Pagini recente » Cod sursa (job #1603542) | Cod sursa (job #350588) | Cod sursa (job #1757464) | Cod sursa (job #352009) | Cod sursa (job #446122)
Cod sursa(job #446122)
#include<fstream.h>
#include<string.h>
char a[2000001],b[2000001];
int urm[2000000],poz[1001],k;
ofstream g("strmatch.out");
void init_urm(char *a)
{
int i=0,j=-1,la=strlen(a);
urm[0] = -1;
while(i<la)
{
while(j>-1 && a[i]!=a[j])j=urm[j];
i++;j++;
if(a[i]==a[j])urm[i]=urm[j];
else urm[i]=j;
}
}
void cauta(char *a, char *b)
{
init_urm(a);
int i=0, j=0, la = strlen(a), lb = strlen(b);
while(j<lb)
{
while(i>-1 && a[i]!=b[j])i=urm[i];
i++;j++;
if(i>=la)
{
poz[++k]=j-i;
i=urm[i];
}
}
}
int main()
{
ifstream f("strmatch.in");
f.get(a,2000001);f.get();f.get(b,2000001);
cauta(a,b);
g<<k<<'\n';
for(int i=1;i<=k;i++)g<<poz[i]<<' ';
f.close();g.close();
return 0;
}