Pagini recente » Monitorul de evaluare | Diferente pentru utilizator/iandrei intre reviziile 7 si 4 | Diferente pentru utilizator/rush intre reviziile 1 si 2 | Cod sursa (job #3312886) | Cod sursa (job #2420080)
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N=(int)2e6+7;
char s[N];
char pat[N];
int ps[N];
int n,m;
void buildPS()
{
ps[0]=1;
int i=1,cur=0;
while(i<m)
{
if(pat[i]==pat[cur])
{
cur++;
ps[i]=cur;
i++;
}
else
{
if(cur==0)
{
i++;
}
else
{
cur=ps[cur-1];
}
}
}
}
int ans[1007],cnt;
void KMP()
{
int i=0;
int j=0;
while(i<n)
{
if(s[i]==pat[j])
{
i++;
j++;
}
if(j==m)
{
cnt++;
if(cnt<=1000)
{
ans[cnt]=i-m;
}
j=ps[j-1];
}
if(i<n && s[i]!=pat[j])
{
if(j==0)
{
i++;
}
else
{
j=ps[j-1];
}
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
cin.getline(pat,N); cin.getline(s,N);
n=strlen(s); m=strlen(pat);
buildPS(), KMP();
cout<<cnt<<"\n";
if(cnt>1000) cnt=1000;
for(int i=1;i<=cnt;i++)
{
cout<<ans[i]<<" ";
}
cout<<"\n";
return 0;
}