Pagini recente » Cod sursa (job #1873099) | Cod sursa (job #2266673) | Cod sursa (job #1559267) | Cod sursa (job #2367607) | Cod sursa (job #170794)
Cod sursa(job #170794)
#include <stdio.h>
#include <string.h>
const int n_max = 2000100;
const int s_max = 1009;
char s1[n_max],
s2[n_max];
int r, sol[s_max], n, m, pi[n_max];
void prefix()
{
int k = 0;
for (int i = 2; i <= n; ++ i)
{
while (k > 0 && s1[k+1]!= s1[i])
k = pi[k];
if (s1[k+1] == s1[i])
pi[i] = ++k;
}
}
void kmp()
{
int k = 0;
for (int i = 1; i <= m; ++ i)
{
while (k > 0 && s1[k+1] != s2[i])
k = pi[k];
if (s2[i] == s1[k+1])
++k;
// printf("%d ", k);
if (k == n)
{
++r;
if (sol[0] < 1000)
sol[++sol[0]] = i-n;
k= pi[k];
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s\n%s\n", s1+1, s2+1);
n = strlen(s1+1);
m = strlen(s2+1);
prefix();
kmp();
printf("%d\n", r);
for (int i = 1; i <= sol[0]; ++ i)
printf("%d ", sol[i]);
return 0;
}