Pagini recente » Cod sursa (job #1927171) | Cod sursa (job #3271486) | Cod sursa (job #15597) | Cod sursa (job #278762) | Cod sursa (job #344359)
Cod sursa(job #344359)
#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;
int sol[1001];
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()+1);
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)
sol[++nr_sol]=i-k+1;
}
}
void afisare()
{
g<<nr_sol<<endl;
for (int i=1; i<=nr_sol; ++i)
g<<sol[i]<<" ";
}
int main()
{
KMP();
afisare();
return 0;
}