Pagini recente » Cod sursa (job #1362023) | Cod sursa (job #1674512) | Cod sursa (job #2510032) | Cod sursa (job #2408041) | Cod sursa (job #1552553)
#include <cstdio>
#include <cstring>
using namespace std;
int phi[2000005] , n , m , v[2000005];
char a[2000005] , b[2000005] ;
void make_phi (char a[2000005] , int n)
{
int k;
phi[1] = 0;
for (int i = 2 ; i <= n ; ++i)
{
k = phi[i - 1];
while (a[i] != a[k + 1] && k > 0)
k = phi[k];
if (a[i] == a[k + 1]) phi[i] = k + 1;
else phi[i] = 0;
}
}
void kmp (char a[2000005] , char b[2000005] , int v[2000005] , int n , int m)
{
make_phi (a , n);
int k;
for (int i = 1 ; i <= m ; ++i)
{
k = v[i - 1];
while (k > 0 && b[i] != a[k + 1])
k = phi[k];
if (b[i] == a[k + 1])
v[i] = k + 1;
else v[i] = 0;
}
}
int main()
{
freopen ("strmatch.in" , "r" , stdin);
freopen ("strmatch.out" , "w" , stdout);
gets (a + 1);
gets (b + 1);
n = strlen (a + 1);
m = strlen (b + 1);
a[n + 2] = '^';
kmp (a , b , v , n , m);
int nr = 0;
for (int i = 1 ; i <= m ; ++i)
if (v[i] == n) nr++;
printf ("%d\n" , nr);
nr = 0;
for (int i = 1 ; i <= m ; ++i)
if (v[i] == n && nr < 1000)
printf("%d " , i-n) , nr++;
return 0;
}