Pagini recente » Cod sursa (job #2425627) | Cod sursa (job #2014488) | Cod sursa (job #1110850) | Cod sursa (job #2111864) | Cod sursa (job #408817)
Cod sursa(job #408817)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 2000005;
int i , j , k , n , m , q;
char A[maxn] , B[maxn];
int rez[1010] , pi[maxn];
void prefix ()
{
int i , q = 0;
for( i = 2 , pi[1] = 0 ; i <= m ; ++i ) {
while ( q && A[q + 1] != A[i] )
q = pi[q];
if ( A[q + 1] == A[i] )
q ++;
pi[i] = q;
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(A,maxn,stdin);
fgets(B,maxn,stdin);
m = strlen(A) - 1;
n = strlen(B) - 1;
for ( i = m ; i >= 1 ; --i ) A[i] = A[i - 1];
for( i = n ; i >= 1 ; --i ) B[i] = B[i - 1];
prefix();
for( i = 1 ; i <= n ; ++i ) {
while ( q && A[q + 1] != B[i] )
q = pi[q];
if ( A[q + 1] == B[i] )
q ++;
if ( q == m ) {
q = pi[m];
k++;
if ( k <= 1000 ) rez[k] = i - m;
}
}
printf("%d\n",k);
for( i = 1 ; i <=min(k,1000) ; ++i )
printf("%d ",rez[i]);
return 0;
}