Pagini recente » Cod sursa (job #1050894) | Cod sursa (job #100841) | Cod sursa (job #2045285) | Cod sursa (job #573821) | Cod sursa (job #653487)
Cod sursa(job #653487)
#include<fstream>
#include<iostream>
#include<cstring>
#define lmax 2000000
using namespace std;
ifstream f("strmatch.in",fstream::in);
ofstream g("strmatch.out",fstream::out);
char a[lmax],b[lmax];
int n,m,q,i,k,urm[lmax],sol[lmax],nrsol;
void next(char a[])
{ int m,k,q;
m=strlen(a);
k=0;
for(q=2;q<=m;q++)
{
while(k && a[k+1]!=a[q])
k=urm[k];
if(a[k+1]==a[q])
k+=1;
urm[q]=k;
}
}
int main()
{ f.getline(b+1,lmax);
f.getline(a+1,lmax);
n=strlen(a+1);
m=strlen(b+1);
next(b+1);
k=0;
for(i=1;i<=n;i++)
{
while(k && b[k+1]!=a[i])
k=urm[k];
if(b[k+1]==a[i])
k+=1;
if(k==m-1 && a[i+1]==b[m])
{
sol[++nrsol]=i-m+1;
k=urm[k];
}
}
g<<nrsol<<"\n";
for(i=1;i<=nrsol;i++)
g<<sol[i]<<" ";
f.close();
g.close();
return 0;
}