題意：給定兩個序列a ,b, 如果在a中存在一段連續的序列使得
a[i]-b[0]==k, a[i+1]-b[1]==k.... a[i+n-1]-b[n-1]==k
就說b串在a串中出現過！最后輸出b串在a串中出現幾次！
思路： KMP變形！如何轉換成KMP求解呢？
舉一個例子說明一下：
a: 5 10 8 10 11 9 11 12 10 15
b: 4 2 4 5 3
根據題意 a中的 10 8 10 11 9 與 b是匹配的， 11 9 11 12 10跟b也是匹配的！
如何將b串以及 10 8 10 11 9， 以及 11 9 11 12 10轉換成同一個串？這樣好套用kmp啊！
因為對應的數值的差值都是相同的！ 令a[i]-=a[i+1], b[i]-=b[i+1]!
這樣也就是將串的長度減少了1，這樣就可以套kmp模板了！
別忘記對特殊情況考慮一下！
1 #include<iostream> 2 #include<cmath> 3 #include<cstdio> 4 #include<algorithm> 5 #include<cstring> 6 #define N 200005 7 using namespace std; 8 9 int f[N], a[N], b[N]; 10 int n, w; 11 void getFail(){ 12 f[0]=0; f[1]=0; 13 for(int i=1; i<w; ++i){ 14 int j=f[i]; 15 while(j && b[i] != b[j]) j=f[j]; 16 if(b[i] == b[j]) f[i+1] = j+1; 17 else f[i+1] = 0; 18 } 19 } 20 21 void findText(){ 22 int j=0; 23 int cnt = 0; 24 for(int i=0; i<n; ++i){ 25 while(j && a[i] != b[j]) j=f[j]; 26 if(a[i] == b[j]) ++j; 27 if( j == w ) ++cnt; 28 } 29 printf("%d\n", cnt); 30 } 31 32 int main(){ 33 scanf("%d%d", &n, &w); 34 for(int i=0; i<n; ++i){ 35 scanf("%d", &a[i]); 36 if(i) a[i-1] -= a[i]; 37 } 38 39 for(int i=0; i<w; ++i){ 40 scanf("%d", &b[i]); 41 if(i) b[i-1] -= b[i]; 42 } 43 if(n==1 && w==1){ 44 printf("%d\n", 1); 45 return 0; 46 } 47 else if(n==1){ 48 printf("%d\n", 0); 49 return 0; 50 } 51 else if( w==1 ){ 52 printf("%d\n", n); 53 return 0; 54 } 55 --n; 56 --w; 57 b[w] = -1e6; 58 getFail(); 59 findText(); 60 return 0; 61 }
?
