思想
KMP的名字是取了三个发明者名字的首字母，用于解决单模式串匹配问题，即给定一个文本串（text）和一个模式串（pattern），在文本串中找出所有与模式串完全相同的位置（或判断是否存在、统计次数等）。
最朴素的办法为双指针，复杂度为。
KMP的基本思路为当我们发现某一个字符不匹配时，由于已经知道之前遍历过的字符，考虑利用这些信息来避免回退这个步骤，即使文本串指针一直向右。
数组的定义为最长公共前后缀用于实现避免回溯的功能，我们通常称为失配数组，建立于模式串之上，用于记录在当前位置失配后应该跳转到哪个位置。
求数组就是个简单的递推。如果相同就自增，如果不同就跳到上一个，也就是最长公共前后缀的最长公共前后缀，即找到原串长度次之的公共前后缀，继续匹配。
复杂度为
题
P3375 【模板】KMP - 洛谷
模板题。
#include<iostream>
#include<queue>
#include<deque>
#include<bitset>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<unordered_map>
#include<set>
#include<map>
#include<ctime>
#include<random>
#include<vector>
#include<utility>
#define f(i,a,b) for(ll i=a;i<=b;i++)
using ll = long long;
using db = double;
ll rd(){ll x=0,w=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-'){w=-1;}c=getchar();}while('0'<=c&&c<='9'){x=x*10+(c-'0');c=getchar();}return x*w;}
using namespace std;
const ll MX =5e5+7;
const ll mod = 1e9+7;
mt19937 mrd(time(0));
namespace Wunsch{
ll n,T,k,m,ans,cnt;
ll nxt[MX];
string s1,s2;
void work(){
cin>>s1>>s2;
s1=" "+s1;
s2=" "+s2;
ll j=0;
f(i,2,s2.size()-1){
while(j&&s2[i]!=s2[j+1])j=nxt[j];
if(s2[i]==s2[j+1])j++;
nxt[i]=j;
}
j=0;
f(i,1,s1.size()-1){
while(j&&s2[j+1]!=s1[i])j=nxt[j];
if(s1[i]==s2[j+1])j++;
if(j==s2.size()-1)cout<<i-s2.size()+2<<endl;
}
f(i,1,s2.size()-1){
cout<<nxt[i]<<" ";
}
return ;
}
bool main(){
T=1;
while(T--)work();
return 1;
}
}
bool amiya=Wunsch::main();
int main(){;}
懒癌犯了明天应该会补一些题，现在去学一会乐理去。
数一数
我以为是神必计数题，没想到剪枝就过了。
设个字符串中长度最小为。
首先发现长度大于的字符串没法作为长度为的字符串的子串，所以答案为。
然后发现存在多个长度为的字符串时如果这些字符串不相等那么他们的答案也为。
所以最多只需要做一次就可以了。
#include<iostream>
#include<queue>
#include<deque>
#include<bitset>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<unordered_map>
#include<set>
#include<map>
#include<ctime>
#include<random>
#include<vector>
#include<utility>
#define f(i,a,b) for(ll i=a;i<=b;i++)
using ll = long long;
using db = double;
ll rd(){ll x=0,w=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-'){w=-1;}c=getchar();}while('0'<=c&&c<='9'){x=x*10+(c-'0');c=getchar();}return x*w;}
using namespace std;
const ll MX =2e6+7;
const ll mod = 998244353;
mt19937 mrd(time(0));
namespace Wunsch{
ll n,T,k,m,ans,cnt,nm;
ll nxt[MX];
ll j;
string s[1000010],ss;
void kmp(ll x){
j=0;
f(i,2,s[x].size()-1){
while(j&&s[x][i]!=s[x][j+1])j=nxt[j];
if(s[x][i]==s[x][j+1])j++;
nxt[i]=j;
}
return ;
}
void work(){
n=rd();
m=1145141919810;
f(i,1,n){
cin>>s[i];
s[i]=" "+s[i];
m=min(m,(ll)s[i].size());
}
ll num=0;
f(i,1,n){
if(s[i].size()==m){
num++;
ss=s[i];
nm=i;
}
}
if(num>1){
f(i,1,n){
if(s[i].size()==m&&s[i]!=ss){
f(o,1,n){
puts("0");
}
return ;
}
}
}
j=0;
kmp(nm);
ans=1;
f(k,1,n){
j=0;
cnt=0;
f(p,1,s[k].size()-1){
while(j&&s[k][p]!=s[nm][j+1])j=nxt[j];
if(s[k][p]==s[nm][j+1])j++;
if(j==s[nm].size()-1){
cnt++;
j=nxt[j];//不加这一步有越界风险，不过大部分时候可有可无
}
}
ans*=cnt;
ans%=mod;
}
f(i,1,n){
if(m!=(ll)s[i].size()){
cout<<"0\n";
}
else {
cout<<ans<<"\n";
}
}
return ;
}
bool main(){
// T=rd();
T=1;
while(T--)work();
return 1;
}
}
bool amiya=Wunsch::main();
int main(){;}
栗酱的数列
还是很简单的，手算算样例就出来了。
考虑转化为差分约束。
设这个公共余数为 ，则对于任意 有
考虑相邻两项的差：
展开得
记
则条件变为
即
#include<iostream>
#include<queue>
#include<deque>
#include<bitset>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<unordered_map>
#include<set>
#include<map>
#include<ctime>
#include<random>
#include<vector>
#include<utility>
#define f(i,a,b) for(ll i=a;i<=b;i++)
using ll = long long;
using db = double;
ll rd(){ll x=0,w=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-'){w=-1;}c=getchar();}while('0'<=c&&c<='9'){x=x*10+(c-'0');c=getchar();}return x*w;}
using namespace std;
const ll MX =2e5+7;
const ll mod = 998244353;
mt19937 mrd(time(0));
namespace Wunsch{
ll n,T,k,m,ans,cnt,nm;
ll nxt[MX];
ll a[MX],b[MX];
ll j;
void work(){
n=rd();m=rd();k=rd();
ans=0;
f(i,1,n)a[i]=rd();
f(i,1,m)b[i]=rd();
f(i,1,n-1){
a[i]=((a[i+1]-a[i])%k+k)%k;
// cout<<a[i]<<" ";
}
// cout<<endl;
f(i,1,m-1){
b[i]=((b[i+1]-b[i])%k+k)%k;
// cout<<b[i]<<" ";
}
// cout<<endl;
j=0;
f(i,2,m-1){
while(j&&b[i]!=b[j+1])j=nxt[j];
if(b[i]==b[j+1])j++;
nxt[i]=j;
}
// ll p=-1;
j=0;
f(i,1,n-1){
while(j&&(a[i]+b[j+1]%k+k)%k!=0)j=nxt[j];
// if(p==-1)p=(a[i]+b[j+1])%k;
if(((a[i]+b[j+1])%k+k)%k==0)j++;
if(j==m-1){
ans++;
j=nxt[j];
// p=-1;
}
}
cout<<ans<<endl;
f(i,1,m-1)nxt[i]=0;
return ;
}
bool main(){
T=rd();
// T=1;
while(T--)work();
return 1;
}
}
bool amiya=Wunsch::main();
int main(){;}