Pagini recente » Cod sursa (job #731068) | Cod sursa (job #1740151) | Cod sursa (job #2261446) | Cod sursa (job #615764) | Cod sursa (job #634598)
Cod sursa(job #634598)
#include <stdio.h>
#include <stdlib.h>
int n, m, pi[2000003];
char str[2000003], s[2000003];
int sol[2000003], id = 0;
int main()
{
FILE *f = fopen("strmatch.in","r");
char c;
fscanf(f, "%c", &c);
int i = 1;
while(c != '\n')
{
s[i++] = c;
fscanf(f, "%c", &c);
}
n = --i;
i = 1;
m = 0;
fscanf(f, "%c", &c);
while (!feof(f))
{
str[i++] = c;
m++;
fscanf(f, "%c", &c);
}
int q = 0;
pi[1] = 0;
for (i = 2; i <= n; i++)
{
while (q > 0 && s[q+1] != s[i])
q = pi[q];
if (s[q+1] == s[i])
q++;
pi[i] = q;
}
q = 0;
for (i = 1; i <= m; i++)
{
while (q > 0 && s[q+1] != str[i])
q = pi[q];
if (s[q+1] == str[i])
q++;
if (q == n)
{
sol[id++] = i - q;
//printf("i = %i, q = %i", i,q);
q = pi[q];
}
}
fclose(f);
f = fopen("strmatch.out","w");
fprintf(f, "%i\n", id);
for (i = 0; i < id; i++)
fprintf(f, "%i ", sol[i]);
fclose(f);
return 0;
}