Pagini recente » Cod sursa (job #2821120) | Cod sursa (job #2756886) | Cod sursa (job #660055) | Cod sursa (job #1906752) | Cod sursa (job #143829)
Cod sursa(job #143829)
#include <stdio.h>
#include <string.h>
const int nm = 1 << 21;
char a[nm], b[nm];
int pi[nm], sol[1000001], cnt;
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
int i, s1, s2, k;
fgets(a, nm, stdin);
s1 = strlen(a) - 1;
fgets(b, nm, stdin);
s2 = strlen(b) - 1;
pi[0] = -1;
k = -1;
for(i = 1; i < s1; ++i)
{
while(k != -1 && a[i] != a[k + 1])
{
k = pi[k];
}
if(a[i] == a[k + 1])
{
++k;
}
pi[i] = k;
//printf("%d %d\n", i, pi[i]);
}
k = -1;
for(i = 0; i < s2; ++i)
{
//printf("%d\n", k);
while(k != -1 && b[i] != a[k + 1])
{
k = pi[k];
}
if(b[i] == a[k + 1])
{
++k;
}
if(k == s1 - 1)
{
sol[++cnt] = i - s1 + 1;
}
}
printf("%d\n", cnt);
if(cnt > 1000)
cnt = 1000;
for(i = 1; i <= cnt; ++i)
{
printf("%d ", sol[i]);
}
return 0;
}