Pagini recente » Cod sursa (job #649745) | Cod sursa (job #2700052) | Cod sursa (job #2815117) | Cod sursa (job #1954241) | Cod sursa (job #2717261)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char A[2000001], B[2000001];
int pi[2000001], pos[1001];
int main(){
f >> (A + 1) >> (B + 1);
int N = strlen(A + 1), M = strlen(B + 1), q = 0, n = 0;
for(int i = 2;i <= N;i++){
while(q && A[q + 1] != A[i])
q = pi[q];
if(A[q + 1] == A[i])
q++;
pi[i] = q;
}
q = 0;
for(int i = 1;i <= M;i++){
while(q && A[q + 1] != B[i])
q = pi[q];
if(A[q + 1] == B[i])
q++;
if(q == N){
q = pi[N], n++;
if(n <= 1000)
pos[n] = i - N;
}
}
g << n << "\n";
for(int i = 1;i <= min(n, 1000);i++)
g << pos[i] << " ";
}