Pagini recente » Cod sursa (job #459381) | Cod sursa (job #540892) | Cod sursa (job #924651) | Cod sursa (job #2979358) | Cod sursa (job #1419221)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
#define maxn 2000007
int p[maxn], sol[1008], nsol;
string a, b;
void prefix()
{
int n = a.size();
int k = 0, i;
p[0] = 0;
for (i = 1; i < n; i++)
{
while( k && a[k] != a[i]) k = p[k];
if (a[k] == a[i]) k++;
p[i] = k;
}
}
void kmp()
{
int k, i;
int n = a.size(), m = b.size();
k = 0;
for (i = 0; i < m; i++)
{
while (k && a[k]!=b[i]) k = p[k];
if (a[k] == b[i]) k++;
if (k == n && nsol < 1000) {sol[nsol++] = i - n + 1; k--;}
}
}
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f>>a>>b;
prefix();
kmp();
g<<nsol<<'\n';
for (int i = 0; i < nsol && i < 1000; i++)
g<<sol[i]<<' ';
}