algorithm - 包含每个子字符串的 dict 单词数

Question

我偶然遇到一个问题，要求用户计算 K 个字符串列表(每个字符串的长度为 M)中 N 个子字符串的匹配词数，并满足以下约束:

0 < length of substring <= 100
0 < M <= 100
0 < N <= 10,000
0 < K <= 10,000

例如:{ serpent, lose, last } 的子字符串 se 将产生 2。

鉴于此输入的巨大范围，检查每个子字符串的所有 K 个字符串的代价太高。由于这个原因，KMP 不起作用。使用后缀树预处理字符串将是下一个更好的选择。但我不可能为每个单词创建后缀树，因为它会再次导致上述问题。即使我尝试将所有单词连接在一起，问题是我无法检测到同一个单词中的子字符串(例如，{stools, sat} 的子字符串 s 将产生 3)。

有没有更有效的方法来解决这个问题？

Answer 1

一种方法是索引要搜索的字符串的每个字符。

“蛇”会给出:

• > {0}
• e > {1, 4}
• r > {2}
• p > {3}
• n > {5}
• t > {6}

由此，对于您在此字符串中搜索的每个单词，在字典中查找其第一个和最后一个字符。

如果找到它们，您需要查看相应的索引以找到可以匹配字符串长度的一对。

一旦找到，您就可以进行完整的字符串比较，但仅限于这种情况。

代码可以是这样的(c#):

static void Main( string[] args )
{
    List<string> words = new List<string>() { "se", "s", "pen", "oo", "st" };
    List<int> scores = new List<int>( words.Select( w => 0 ) );

    List<string> strings = new List<string>() { "serpent", "lose", "last", "stools", "sat" };

    foreach ( var s in strings )
    {
        var indexes = MakeIndexes( s );

        for ( int i = 0 ; i < words.Count ; i++ )
        {
            scores[i] += Score( words[i], s, indexes );
        }
    }
}

static int Score( string word, string s, Dictionary<char, List<int>> indexes )
{
    int firstPos = 0, lastPos = word.Length - 1;
    char first = word[firstPos];
    char last = word[lastPos];

    List<int> firstIndexes;
    if ( indexes.TryGetValue( first, out firstIndexes ) )
    {
        if ( firstPos == lastPos )
            return 1;
        else
        {
            List<int> lastIndexes;
            if ( indexes.TryGetValue( last, out lastIndexes ) )
            {
                int fiPos = 0, liPos = 0;

                while ( fiPos < firstIndexes.Count && liPos < lastIndexes.Count )
                {
                    int fi = firstIndexes[fiPos], li = lastIndexes[liPos];
                    int len = li - fi;

                    if ( len < lastPos )
                        liPos++;
                    else if ( len == lastPos )
                    {
                        if ( FullCompare( word, s, fi ) )
                            return 1;
                        fiPos++;
                        liPos++;
                    }
                    else
                        fiPos++;
                }
            }
        }
    }

    return 0;
}

static bool FullCompare( string word, string s, int from )
{
    for ( int i = 0 ; i < word.Length ; i++ )
        if ( word[i] != s[i + from] )
            return false;
    return true;
}

static Dictionary<char, List<int>> MakeIndexes( string s )
{
    Dictionary<char, List<int>> result = new Dictionary<char, List<int>>();

    for ( int i = 0 ; i < s.Length ; i++ )
    {
        char c = s[i];

        List<int> indexes;
        if ( result.TryGetValue( c, out indexes ) == false )
        {
            indexes = new List<int>();
            result.Add( c, indexes );
        }

        indexes.Add( i );
    }

    return result;
}