Pagini recente » Cod sursa (job #562411) | Cod sursa (job #1841205) | Cod sursa (job #2965608) | Cod sursa (job #389160) | Cod sursa (job #748499)
Cod sursa(job #748499)
#include <stdio.h>
#include <string.h>
char a[2000001];
char b[2000001];
int n,m;
int app[1024], k;
int next[2000000];
void calc_next()
{
int i,j = 0;
for(i = 2;i < n;i++)
{
while( j && a[j] != a[i])
j = next[j];
if(a[j] == a[i])
j++;
next[i] = j;
}
}
inline int minim(int a, int b)
{ return a<=b?a:b;}
int main()
{
FILE *f = fopen("strmatch.in","r");
fscanf(f, "%s",a);
fscanf(f, "%s",b);
fclose(f);
n = strlen(a);
m = strlen(b);
calc_next();
int i,j = 0;
for(i=0;i<m;i++)
{
while(j && b[i] != a[j])
j = next[j];
if( b[i] == a[j])
j++;
if(j==n)
{
j = next[n - 1];
if(k < 1000)
app[k++] = i - n +1;
}
}
f = fopen("strmatch.out","w");
fprintf(f, "%d\n",k);
for(i=0;i< minim(1000,k);i++)
fprintf(f, "%d ", app[i]);
fclose(f);
return 0;
}