Pagini recente » Cod sursa (job #2831078) | Cod sursa (job #680695) | Cod sursa (job #2975486) | Cod sursa (job #1422381) | Cod sursa (job #719199)
Cod sursa(job #719199)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define MAXL 2000001
char A[MAXL],B[MAXL];
int f[MAXL],i,j,n,m,nr;
vector<int> rez;
void preg_kmp() {
int stare;
f[0]=-1;
stare=-1;
for(i=1;i<=m;i++) {
while ( (stare>=0)&&(A[stare+1]!=A[i]) ) stare=f[stare];
if (A[stare+1]==A[i]) f[i]=stare+1;
else f[i]=-1;
stare=f[i];
}
}
int main() {
fin.getline(A,MAXL);
fin.getline(B,MAXL);
for(m=MAXL;A[m]==0;m--) {}
for(n=MAXL;B[n]==0;n--) {}
preg_kmp();
//for(i=0;i<=m;i++) cout<<f[i]<<" ";
//cout<<"\n";
//cout<<A<<"\n"<<B<<"\n";
//cout<<m<<" "<<n<<"\n";
nr=0;
int stare=-1;
for(i=0;i<=n;i++) {
while ( (stare>=0) && (A[stare+1]!=B[i]) ) stare=f[stare];
if (A[stare+1]==B[i]) stare++;
if (stare==m) {
nr++;
if (rez.size()<1000) rez.push_back(i-m);
}
//cout<<B[i]<<"("<<i<<")"<<" "<<A[stare]<<"("<<stare<<")"<<"\n";
}
fout<<nr<<"\n";
for(i=0;i<rez.size();i++) fout<<rez[i]<<" ";
fout<<"\n";
fout.close();
return 0;
}