Pagini recente » Cod sursa (job #2318780) | Cod sursa (job #3163302) | Cod sursa (job #2363060) | Cod sursa (job #151198) | Cod sursa (job #2409731)
#include<bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int DIM = 2e6 + 10;
int P[DIM], Ans[DIM], Sol, L, N1, N2;
char S1[DIM], S2[DIM];
int main(){
fin.getline( S1 + 1, DIM - 5 );
fin.getline( S2 + 1, DIM - 5 );
N1 = strlen( S1 + 1 );
N2 = strlen( S2 + 1 );
P[1] = 0;
L = 0;
for( int i = 2; i <= N1; i++ ){
while( L != 0 && S1[L + 1] != S1[i] )
L = P[L];
if( S1[L + 1] == S1[i] )
L++;
P[i] = L;
}
L = 0;
for( int i = 1; i <= N2; i++ ){
while( L != 0 && S1[L + 1] != S2[i] )
L = P[L];
if( S1[L + 1] == S2[i] )
L++;
if( L == N1 ){
Ans[++Sol] = i - N1;
L = P[L];
}
}
fout << Sol << "\n";
Sol = min( Sol, 1000 );
for( int i = 1; i <= Sol; i++ )
fout << Ans[i] << " ";
return 0;
}