Pagini recente » Cod sursa (job #1586425) | Cod sursa (job #436924) | Cod sursa (job #2941495) | Cod sursa (job #1529005) | Cod sursa (job #1429675)
#include <fstream>
#include <algorithm>
#include <cstring>
#define DIM 2097152
using namespace std;
ifstream fin ("strmatch.in" );
ofstream fout("strmatch.out");
int N, M, C[DIM], P[DIM], i; char A[DIM], B[DIM];
inline void KMP(char A[], char B[], int C[], int P[], int N, int M){
int L = 0, i;
for(i = 2; i <= N; i ++){
while(L != 0 && A[i] != A[L+1])
L = P[L];
if(A[i] == A[L+1])
L ++;
P[i] = L;
}
L = 0;
for(i = 1; i <= M; i ++){
while(L != 0 && B[i] != A[L+1])
L = P[L];
if(B[i] == A[L+1])
L ++;
if(L == N){
C[++C[0]] = i - N;
L = P[L];
}
}
return;
}
int main(){
fin >> A + 1;
N = strlen(A + 1);
fin >> B + 1;
M = strlen(B + 1);
KMP(A, B, C, P, N, M);
fout << C[0] << "\n";
for(i = 1; i <= min(C[0], 1000); i ++)
fout << C[i] << " ";
return 0;
}