Pagini recente » Cod sursa (job #850643) | Cod sursa (job #567037) | Cod sursa (job #2665621) | Cod sursa (job #2418991) | Cod sursa (job #467906)
Cod sursa(job #467906)
#include <fstream>
#include <iostream>
#include <vector>
#include <string>
#define DN 2000001
using namespace std;
int pr[DN],m;
string a,b;
void p() {
int k=0,q;
m=a.size();
--m;
for(q=2; q<=m; q++) {
while( k && a[k+1]!=a[q])
k=pr[k];
if(a[k+1]==a[q]) ++k;
pr[q]=k;
}
}
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
vector<int> sol;
vector<int>::iterator it;
string c,d;
int i,q=0,n,cont=0;
a=" ",b=" ";
f>>c;
f.get();
f>>d;
a+=c;
b+=d;
n=b.size();
--n;
p();
///<kmp>
for(i=0; i<n; i++) {
for( ;q>0 && a[q+1]!=b[i]; q=pr[q]);
if(a[q+1]==b[i]) ++q;
if(q==m) {
++cont;
sol.push_back(i-m);
}
}
///</kmp>
g<<cont<<"\n";
for(it=sol.begin(),i=0;i<=1000 && it!=sol.end(); i++,it++) g<<*it<<" ";
g<<"\n";
f.close();
g.close();
return 0;
}