Pagini recente » Cod sursa (job #891658) | Cod sursa (job #470904) | Cod sursa (job #259473) | Cod sursa (job #3268027) | Cod sursa (job #467913)
Cod sursa(job #467913)
#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;
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>>a;
f.get();
f>>b;
m=a.size();
n=b.size();
for (i = m; i; --i) a[i] = a[i-1]; a[0] = ' ';
for (i = n; i; --i) b[i] = b[i-1]; b[0] = ' ';
p();
///<kmp>
for(i=1; 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;
}