Pagini recente » Cod sursa (job #1503021) | Cod sursa (job #497489) | Cod sursa (job #1606962) | Cod sursa (job #654266) | Cod sursa (job #344357)
Cod sursa(job #344357)
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
using namespace std;
fstream f("strmatch.in", ios::in);
fstream g("strmatch.out", ios::out);
string a;
string b;
vector<int > next;
vector<int > sol;
int nr_sol;
void KMP()
{
f>>a>>b;
int n=a.size();
a.resize(n+1);
for (int i=n; i>=0; --i)
a[i+1]=a[i];
int m=b.size();
b.resize(m+1);
for (int i=n; i>=0; --i)
b[i+1]=b[i];
next.resize(a.size());
next[1]=0;
int k=0;
for (int i=2; i<=n; ++i)
{
while (k>0 && a[k+1]!=a[i]) k=next[k];
if (a[k+1]==a[i]) ++k;
next[i]=k;
}
k=0;
for (int i=1; i<=m; ++i)
{
while (k>0 && a[k+1]!=b[i]) k=next[k];
if (a[k+1] == b[i]) ++k;
if (n==k)
if (nr_sol < 1000)
{
++nr_sol;
sol.push_back(i-k+1);
}
}
}
void afisare()
{
g<<nr_sol<<endl;
vector<int >::iterator it;
for (it=sol.begin(); it<sol.end(); it++)
g<<*it<<" ";
}
int main()
{
KMP();
afisare();
return 0;
}