Pagini recente » Cod sursa (job #1031757) | Cod sursa (job #873170) | Cod sursa (job #3250317) | Cod sursa (job #2004035) | Cod sursa (job #1198971)
#include<iostream>
#include<fstream>
#include<string.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int i,j,n,m,k,v[2000002],u[200002];
char s[20000000],t[20000000];
void repetitie()
{
u[0]=0;
j=1;
for(i=1;i<n;i++)
{
if(s[i]==s[i-j])u[i]=i-j+1;
else {j=i+1;u[i]=0;}
}
}
void parcurg()
{
if(s[0]==t[0]){v[0]=0;j=1;}
else {j=0;v[0]=-1;}
k=0;
for(i=1;i<=m&&k<1001;i++)
{
if(j==n){k++;j=u[v[i-1]];}
if(s[j]==t[i])
{
v[i]=v[i-1]+1;
if(v[i]==n)v[i]=j;
j++;
}
else
{
if(s[u[v[i-1]]]==t[i]){j=u[v[i-1]];v[i]=u[v[i-1]];j++;}
else {v[i]=-1;j=0;}
}
}
}
int main()
{
f>>s;
f>>t;
n=strlen(s);
m=strlen(t);
repetitie();
parcurg();
//cout<<t<<endl;
//for(i=0;i<m;i++)cout<<v[i];
//cin>>n;
g<<k<<'\n';
k=0;
for(i=0;i<m&&k<1000;i++)if(v[i]==n-1){g<<i-n+1<<' ';k++;}
g.close();
return 0;
}