描述

给你两个串A，B，可以得到从A的任意位开始的子串和B匹配的长度。

给定K个询问，对于每个询问给定一个x，求出匹配长度恰为x的位置有多少个。

N，M，K<=200000

输入格式

第一行三个数 N，M，K，表示A的长度、B的长度和询问数。

第二行为串A。

第三行为串B。

接下来K行，每行1个数X。

输出格式

对于每个询问输出一个数。

测试样例1

输入

6 2 2 

aabcde 

ab 

0 

2

输出

4 

1

代码

1 #include 
       
         2 #include 
        
          3 #include 
         
           4 char a[200000], b[200000]; 5 int next[200000]; 6 int used[200001]; 7 int num[200000]; 8 int kmp[200000]; 9  10 int main(int argc, char **argv)11 {12     int i, j;13     int l1, l2, s;14 //  freopen("input.txt", "r", stdin);15 //  freopen("output.txt", "w", stdout);16     scanf("%d%d%d\n", &l1, &l2, &s);17     scanf("%s\n%s", a, b);18  19     i = 0, j = -1;20     next[0] = -1;21     while(i < l2){22         if(j == -1 || b[i] == b[j]){23             if(b[i + 1] == b[j + 1]){24                 next[i + 1] = next[j + 1];25             }else{26                 next[i + 1] = j + 1;27             }28             kmp[i + 1] = j + 1;29             i++, j++;30         }else{31             j = next[j];32         }33     }34  35     i = 0, j = 0;36     while(i < l1){37         if(j == -1 || a[i] == b[j]){38             num[i] = j + 1;39             used[j + 1]++;40             i++, j++;41         }else{42             j = next[j];43         }44     }45     for(i = l2; i >= 1; i--){46         used[kmp[i]] += used[i];47     }48     for(i = 0; i < s; i++){49         scanf("%d", &j);50         printf("%d\n", used[j] - used[j + 1]);51     }52     return 0;53 }
         
        
       

首先，这个题如果想要求出从每个位置开始的字串的匹配长度，那么O(n^2)以内的算法应该是很难的。但是，这个题要求的并不是“每个位置的长度”，而是“具有这样长度的位置数”。因而，灵活使用KMP算法自我匹配的性质，就能够解决这个问题。

考虑下面的例子：

A串：abbabbabababbababba

B串：abbabababba

应用KMP算法，很容易得到B串的自我匹配是

元素 a b b a b a b a b b  a

位置 1 2 3 4 5 6 7 8 9 10 11

长度 0 0 0 1 2 1 2 1 2 3  4

这个数组记为kmp[位置] = 匹配长度。

由此求得到A串的各个元素尾部的匹配长度是

a b b a b b a b a b a b b  a  b a b b a

1 2 3 4 5 3 4 5 6 7 8 9 10 11 5 6 7 3 4

统计出各个长度的出现频数

长度 0 1 2 3 4 5 6 7 8 9 10 11

频数 0 1 1 3 3 3 2 2 1 1 1  1

这个数组记作cnt[长度] = 频数。

根据KMP自我匹配数组的性质，如果以A串某个元素结尾有一个长度为11的字串可以与B串匹配的话，以该元素结尾的长度为kmp[11] = 4的字串也是可以匹配的。所以说cnt[4] += cnt[11]。也就是说，进行这样的操作

for (i = N; i >= 1; i--)

　　cnt[kmp[i]] += cnt[i];

for i := N downto 1 do

 inc( cnt[ kmp[i] ] , cnt[i] );

//转载者注，inc(i)==i++

之后，cnt[i]中保存的就应该是所有长度为i的匹配字串了。这时cnt数组的状态是

长度 0  1 2 3 4 5 6 7 8 9 10 11

频数 19 8 7 4 4 3 2 2 1 1 1  1

然而题中要求的是“长度恰好为i”的子串的个数，也就是这些字串的下一个字符是不能匹配的。然而，cnt数组中存储的cnt[i]，必然包含了cnt[i + 1]及以上的情况。然而这很简单，“长度恰好为i”的字串数量就是cnt[i] - cnt[i + 1]，因为cnt[i]中可以扩展的字串必然都包含于cnt[i + 1]。