相关疑难解决方法(0)

为什么以下代码会导致:

'the'有1场比赛

并不是:

'the'共有3场比赛

using System;
using System.Text.RegularExpressions;

namespace TestRegex82723223
{
    class Program
    {
        static void Main(string[] args)
        {
            string text = "C# is the best language there is in the world.";
            string search = "the";
            Match match = Regex.Match(text, search);
            Console.WriteLine("there was {0} matches for '{1}'", match.Groups.Count, match.Value);
            Console.ReadLine();
        }
    }
}

我刚接触到一个采访问题:找到一个给定字符串中所有重复的子字符串,其最小大小为2.该算法应该是高效的.

上面给出了上述问题的代码,但效率不高.

#include <iostream>
#include <algorithm>
#include <iterator>
#include <set>
#include <string>

using namespace std;

int main()
{
    typedef string::const_iterator iterator;
    string s("ABCFABHYIFAB");
    set<string> found;

    if (2 < s.size())
        for (iterator i = s.begin() + 1, j = s.end(); i != j; ++i)
            for (iterator x = s.begin(); x != i; ++x)
            {
                iterator tmp = mismatch(i, j, x).second;;
                if (tmp - x > 1)
                    found.insert(string(x, tmp));
            }

            copy(found.begin(), found.end(),ostream_iterator<string>(cout, "\n"));
}

我的问题是,是否有任何数据结构可以在O(N)的时间复杂度上实现上述问题？

如果您的答案是后缀树或哈希,请详细说明.