Pagini recente » Cod sursa (job #2952162) | Cod sursa (job #332406) | Cod sursa (job #1724368) | Cod sursa (job #1414822) | Cod sursa (job #159941)
Cod sursa(job #159941)
#include <stdio.h>
#include <string.h>
#define lmax 2000005
char s[lmax],w[lmax];
int n,m,nr,a[lmax],t[lmax];
void prep();
FILE *f,*g;
int main()
{
int i,j;
f=fopen("strmatch.in","rt");
g=fopen("strmatch.out","wt");
fgets(w, lmax, f);
fgets(s, lmax, f);
s[strlen(s)-1] = 0;
w[strlen(w)-1] = 0;
n=strlen(s);
m=strlen(w);
prep();
i=0;j=0;
while (i+j<n)
{
if (s[i+j]==w[j])
j++;
else
{
i+=j-t[j];
if (j > 0)
j = t[j];
}
if (j==m)
a[++nr]=i;
}
fprintf(g, "%d\n", nr);
for (i = 0; i < nr; i++)
fprintf(g, "%d ", a[i+1]);
fclose(f);
fclose(g);
return 0;
}
void prep()
{
int i,j;
t[0]=-1;
t[1]=0;
i=2;
while (i<=m)
{
j=t[i-1];
while (w[j] != w[i-1] && j != -1)
j = t[j];
t[i++] = j + 1;
j=t[j];
}
}