Pagini recente » Cod sursa (job #2152279) | Cod sursa (job #1359925) | Cod sursa (job #1279161) | Cod sursa (job #2980464)
/// strmatch de pe infoarena cu KMP
#include <fstream>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
char v[4000002];
int pi[2000001];
int sol[1001];
int main()
{
int n=0,i=0,l,nrap=0;
char ch;
cin.get(ch);
while(ch!='\n')
{
v[++n]=ch;
cin.get(ch);
}
l=n;
n++;
v[n]='#';
for(i=2;i<n;i++)
{
pi[i]=pi[i-1];
while(pi[i]!=0 && v[pi[i]+1]!=v[i])
{
pi[i]=pi[pi[i]];
}
if(v[pi[i]+1]==v[i])
pi[i]++;
}
i=n;
pi[n]=0;
n++;
while(cin.get(v[n]))
{
i++;
pi[i]=pi[i-1];
while(pi[i]!=0 && v[pi[i]+1]!=v[n])
{
pi[i]=pi[pi[i]];
}
if(v[pi[i]+1]==v[n])
pi[i]++;
if(pi[i]==l)
{
nrap++;
if(nrap<=1000)
sol[nrap]=i-l-l-1;
}
n++;
}
n-=2;
cout<<nrap;
cout<<'\n';
for(i=1;i<=nrap;i++)
cout<<sol[i]<<" ";
cout<<'\n';
return 0;
}