Pagini recente » Cod sursa (job #190753) | Cod sursa (job #1614587) | Cod sursa (job #2818613) | Cod sursa (job #3266482) | Cod sursa (job #1912371)
#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;
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;
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++]=i-n;
}
}
int main()
{
ifstream f("strmatch.in");
f>>(a+1)>>(b+1);
S(a,b);
ofstream g("strmatch.out");
g<<dim<<'\n';
for(i=0;i<dim;++i)
g<<poz[i]<<" ";
return 0;
}