Pagini recente » Cod sursa (job #1781578) | Cod sursa (job #3287448) | Cod sursa (job #1427675) | Cod sursa (job #2302894) | Cod sursa (job #889236)
Cod sursa(job #889236)
#include<cstdio>
#include<cstring>
#include<fstream>
#define MAX 2000002
using namespace std;
char N[MAX] ,M[MAX] ;
int pi[MAX] , k , n , m , nr , poz[1001];
void citire();
void prefix();
void kmp();
void tipar();
int main()
{
citire();
prefix();
kmp();
tipar();
return 0;
}
void citire()
{
freopen("strmatch.in" , "r" , stdin );
scanf("%s\n%s" , N+1 , M+1 );
n = m = 1;
for(;N[n]; ++n);n--;
for(;M[m]; ++m);m--;
}
void prefix()
{
k = 0;
for( int i = 2 ; i <= n ; ++i )
{
while(k && N[k+1] != N[i])
k = pi[k];
if(N[i] == N[k+1])
k++;
pi[i] = k;
}
}
void kmp()
{
k = 0;
for( int i = 1 ; i <= m ; ++i )
{
while(k && N[k+1] != M[i])
k = pi[k];
if(M[i] == N[k+1])
k++;
if(k == n )
{
nr++;
if(nr<=1000)
poz[nr] = i-n;
}
}
}
void tipar()
{
freopen("strmatch.out" , "w" , stdout );
printf("%d\n" , nr );
for( int i = 1 ; i <= min(nr,1000) ; ++i )
printf("%d ",poz[i]);
}