Pagini recente » Cod sursa (job #1374396) | Cod sursa (job #2754872) | Monitorul de evaluare | Cod sursa (job #1618914) | Cod sursa (job #3253048)
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char A[4000004], B[2000002];
int N, M, pi[4000002], sol, ans[1002];
int main(){
in >> A;
N = strlen(A);
in >> B;
M = strlen(B);
if(N == 1){
for(int i = 0; i < M; i++){
if(A[0] == B[i]){
sol = sol + 1; ans[sol] = i;
}
}
}
else{
A[N] = '#';
for(int i = 0; i < M; i++) A[N + i + 1] = B[i];
M = M + N + 1;
pi[0] = 0;
for(int i = 1; i < M; i++){
int j = pi[i - 1];
while(j > 0 and A[i] != A[j])
j = pi[j - 1];
if(A[i] == A[j]) j = j + 1;
if(j == N){
sol = sol + 1; ans[sol] = i - N - N;
}
pi[i] = j;
}
}
out << sol << "\n";
for(int i = 1; i <= min(sol, 1000); i++) out << ans[i] << " ";
return 0;
}