Pagini recente » Cod sursa (job #2299822) | Cod sursa (job #1772782) | Cod sursa (job #1227010) | Cod sursa (job #2879362) | Cod sursa (job #2469606)
//wish me luck
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int NMAX = 2000005;
string A,B;
int n,m;
int pi[NMAX];
vector <int> ans;
void make_prefix(){
int q = 0, i;
pi[1] = 0;
for(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;
}
}
int main(){
int i,q = 0;
f >> A >> B;
n = A.size();
m = B.size();
A = ' ' + A;
B = ' ' + B;
make_prefix();
for(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];
if(ans.size() < 1000)
ans.push_back(i - n);
}
}
g << ans.size() << "\n";
for(auto it: ans)
g << it << " " ;
return 0;
}