题目链接：https://nanti.jisuanke.com/t/15500
解析：裸的KMP，先把模式串求出来，然后进行KMP
代码：
#include<bits/stdc++.h> #define N 1000009 using namespace std; typedef long long LL; char p[N], s[N]; int w[N], nx[N]; void cal_next(char p[], int len) { int i, j; nx[0] = 0; for(i = 1; i < len; i++) { j = nx[i - 1]; while(j > 0 && p[i] != p[j]) j = nx[j - 1]; if(p[i] == p[j]) j++; nx[i] = j; } } int KMP(char s[], int len1, char p[], int len2) { int i, j; i = j = 0; int ans = 0; while(i < len1) { if(s[i] == p[j]) i++, j++; else { if(j == 0) i++; else j = nx[j - 1]; } if(j == len2) { ans++; j = nx[j - 1]; } } if(j == len2) ans++; return ans; } int main() { int n, a, b, L, R; scanf("%d%d%d%d%d", &n, &a, &b, &L, &R); w[0] = b; for(int i = 1; i < n; i++) w[i] = (w[i-1]+a) % n; for(int i = 0; i < n; i++) { if((L <= w[i] && w[i] <= R)) { if(!(w[i]&1)) s[i] = 'A'; else s[i] = 'T'; } else if(w[i]&1) s[i] = 'C'; else s[i] = 'G'; } s[n] = '\0'; scanf(" %s", p); int len1 = n, len2 = strlen(p); cal_next(p, len2); int ans = KMP(s, len1, p, len2); printf("%d\n", ans); return 0; }
