这是1道模板题
其实这道题一拿到,看一下数据暴力貌似能过
然而,少年你天真了不开 O2 暴力过不了啊
开了 O2 算作弊( ⊙ o ⊙ )啊!
所以,我们要用kmp
kmp咋写? 看友链
Code
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
int n,m,next[10002];char a[10002],b[100002];
int main()
{
int i,j;
cin>>n>>a>>m>>b;
n=strlen(a);
m=strlen(b);
nex[1]=0;
for(i=n;i>0;i--)swap(a[i],a[i-1]);
for(i=m;i>0;i--)swap(b[i],b[i-1]);
//cout<<a<<" "<<b;
for(i=2,j=0;i<=n;i++)
{
while(j>0&&a[i]!=a[j+1])j=next[j];
if(a[i]==a[j+1])j++;
next[i]=j;
//cout<<j<<endl;
}
for(i=1,j=0;i<=m;i++)
{
while(j>0&&(j==n||b[i]!=a[j+1]))j=next[j];
if(b[i]==a[j+1])j++;
//cout<<j<<endl;
if(j==n)cout<<i-n<<" ";
}
return 0;
}
本机正常
交上去->CE++
Why?
next不能用
好吧,改!
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
int n,m,nex[10002];char a[10002],b[100002];
int main()
{
int i,j;
cin>>n>>a>>m>>b;
n=strlen(a);
m=strlen(b);
nex[1]=0;
for(i=n;i>0;i--)swap(a[i],a[i-1]);
for(i=m;i>0;i--)swap(b[i],b[i-1]);
//cout<<a<<" "<<b;
for(i=2,j=0;i<=n;i++)
{
while(j>0&&a[i]!=a[j+1])j=nex[j];
if(a[i]==a[j+1])j++;
nex[i]=j;
//cout<<j<<endl;
}
for(i=1,j=0;i<=m;i++)
{
while(j>0&&(j==n||b[i]!=a[j+1]))j=nex[j];
if(b[i]==a[j+1])j++;
//cout<<j<<endl;
if(j==n)cout<<i-n<<" ";
}
return 0;
}
gooooooooooooooooooooooooooooooooooooooooooooooooood