Pagini recente » Cod sursa (job #3307599) | Cod sursa (job #3353897) | Cod sursa (job #3320604) | Cod sursa (job #3301226) | Cod sursa (job #3310907)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int Nmax=2e6+5;
string s, t, S;
int cnt;
int nrsol;
int sol[Nmax];
int pi[Nmax*2+1];
int main(){
fin>>t>>s;
S=t+'#'+s; // t1 t2 t3 .. tn # s1 s2 s3 ... sm
// construim pi
pi[0]=0;
int n=S.size();
for (int i=1; i<n; i++){
int j=pi[i-1];
while (j>0 && S[i]!=S[j])
j=pi[j-1];
if (S[i] == S[j])
j++;
pi[i]=j;
}
for (int i=0; i<n; i++)
if (pi[i]==t.size())
sol[nrsol++]=i-2*t.size();
fout<<nrsol<<'\n';
for (int i=0; i<min(nrsol, 1000); i++)
fout<<sol[i]<<' ';
return 0;
}