对于文法子串,这个事实是正确的吗?

本文关键字:事实 于文法 文法 子串 | 更新日期: 2023-09-27 18:01:46

我想写一个算法,找到一个字符串的异义子字符串的数量。例如,字符串"abba"有4:

(1) "a", "a"

(2) "b", "b"

(3) "ab", "ba"

(4) "abb", "bba"

我想要优化的一个事实是

如果一个字符串没有长度为k的字符对子串,那么它就没有长度为k+1

的字符对子串

你能证实这是真的还是假的吗?

因为我的算法
static int NumAnagrammaticalPairs(string str)
{
    int count = 0; // count of anagrammatical pairs found
    int n = str.Length / 2; // OPTIMIZATION: only need to look through the substrings of half the size or less
    for(int k = 1; k <= n; ++k) 
    {
        // get all substrings of length k
        var subsk = GetSubstrings(str,k).ToList();
        // count the number of anagrammatical pairs
        var indices = Enumerable.Range(0, subsk.Count);
        int anapairs = (from i in indices
                        from j in indices
                        where i < j && IsAnagrammaticalPair(subsk[i], subsk[j])
                        select 1).Count();
        // OPTIMIZATION: if didn't find any anagrammatical pairs in the substrings of length k, 
        // there are no anagrammatical pairs in the substrings of length k+1, so we can exit
        // the loop early
        if(anapairs == 0)
            break;
        else
            count += anapairs;
    }
    return count;       
}

得到的结果稍微偏离(通常偏离1)测试用例中的实际结果。

对于文法子串,这个事实是正确的吗?

情况并非如此- abcdcdab是长度为4的字谜,但您找不到长度为3的字谜子串。具体地说,abcdab将不起作用,因为它包含abcdcdab,但没有3个字谜(来自abc, bcd, cda, dab)。