Pagini recente » Cod sursa (job #1683019) | Cod sursa (job #17668) | Cod sursa (job #1787047) | Cod sursa (job #1129757) | Cod sursa (job #2009142)
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int kMaxN = 2000001;
string A,B;
int pi[kMaxN];
int sol[1002];
int ans;
int main(){
in>>A>>B;
unsigned w = 0;
for(unsigned i=1; i<A.size(); i++) {
while(w && A[i] != A[w]) w=pi[w-1];
if(A[i] == A[w]) w++;
pi[i] = w;
}
w = 0;
for(unsigned i=0; i<B.size(); i++) {
while(w && B[i] != A[w]) w=pi[w-1];
if(B[i] == A[w]) w++;
if(w==A.size()){
ans++;
sol[min(ans,1001)] = i-A.size()+1;
}
}
out<<ans<<'\n';
for(int i=1;i<=min(1000,ans);i++) out<<sol[i]<<' ';
return 0;
}