Pagini recente » Cod sursa (job #968612) | Cod sursa (job #1244211) | Cod sursa (job #2011557) | Cod sursa (job #2600791) | Cod sursa (job #1920525)
#include <iostream>
#include<fstream>
#include<cstring>
using namespace std;
#define N 2000200
int n,m,i,j,phi[N],poz[1010],dim,k;
char a[N],b[N];
void phi_compute(char v[])
{
int len=strlen(v+1);
phi[1]=0;
k=0;++len;
for(int i=2;i<len;++i)
{
while(v[i]!=v[ k+1 ] && k )
k=phi[k];
if(v[k+1]==v[i])
++k;
phi[i]=k;
}
}
void S(char v[],char w[])
{
phi_compute(v);
n=strlen(v+1);m=strlen(w+1);
dim=0;k=0;
++m;--n;
for(int i=1;i<m;++i)
{
while(k && v[k+1]!=w[i])
k=phi[k];
if(v[k+1]==w[i])
++k;
if(k>n && dim++<1000)
poz[dim-1]=i-n+1;
}
}
int main()
{
ifstream f("strmatch.in");
f>>(a+1)>>(b+1);
S(a,b);
ofstream g("strmatch.out");
g<<dim<<'\n';
dim=min(1000,dim);
for(i=0;i<dim;++i)
g<<poz[i]<<' ';
return 0;
}