Pagini recente » Cod sursa (job #2494479) | Cod sursa (job #874543) | Cod sursa (job #472536) | Cod sursa (job #1609835) | Cod sursa (job #161487)
Cod sursa(job #161487)
#include <stdio.h>
#include <string.h>
int n, m;
char s1[2000001], s2[2000001];
int p[2000002];
int nrsol;
int o[2000001];
int i, j, k;
void Prefix();
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s %s", &s1, &s2);
n = strlen(s1);
m = strlen(s2);
Prefix();
k = 0;
for ( i = 0; i < m; i++ )
{
while ( k > 0 && s1[k] != s2[i] )
k = p[k];
if ( s1[k] == s2[i] ) k++;
if ( k == n )
{
nrsol++;
o[nrsol] = i-n+1;
}
}
printf("%d\n", nrsol);
for ( i = 1; i < nrsol; i++ )
printf("%d ", o[i]);
printf("%d\n", o[nrsol]);
return 0;
}
void Prefix()
{
p[1] = 0; k = 0;
for ( i = 1; i < n; i++ )
{
while ( k > 0 && s1[k] != s1[i] )
k = p[k];
if ( s1[k] == s1[i] ) k++;
p[i+1] = k;
}
}