Pagini recente » Cod sursa (job #2973668) | Cod sursa (job #2088883) | Cod sursa (job #2506806) | Cod sursa (job #2008830) | Cod sursa (job #693664)
Cod sursa(job #693664)
#include<fstream>
int urm[2000002],n,m,i,x=-1,c[2000002],q;
char a[2000002],b[2000002];
void urmatorul(char *b)
{
int k=-1 ,x;
urm[0]=0;
for(x=1;x<m;x++)
{
while(k>0 && b[k+1]!=b[x])k=urm[k];
if(b[k+1]==b[x])k++;
urm[x]=k;
}
}
using namespace std;
int main()
{
ifstream f("strmatch.in");ofstream g("strmatch.out");
f.getline(b,1000); m=strlen(b);
f.getline(a,1000); n=strlen(a);
urmatorul(b);
for(i=0;i<n;i++)
{
while(x>0 && b[x+1]!=a[i]) x=urm[x];
if(b[x+1]==a[i])x++;
if(x==m-1)
{
c[++q]=i-m+1;
x=urm[x];
}
}
g<<q<<'\n';
for(i=1;i<=q;i++) g<<c[i]<<' ';
f.close();g.close();
return 0;}