Pagini recente » Cod sursa (job #729806) | Cod sursa (job #2506727) | Cod sursa (job #824999) | Cod sursa (job #3263654) | Cod sursa (job #467908)
Cod sursa(job #467908)
#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;
if(cont<=1000)
sol.push_back(i-m);
}
}
///</kmp>
g<<cont<<"\n";
for(it=sol.begin();it!=sol.end();it++) g<<*it<<" ";
g<<"\n";
f.close();
g.close();
return 0;
}