Pagini recente » Cod sursa (job #1438364) | Cod sursa (job #1004399) | Cod sursa (job #2671522) | Cod sursa (job #1161834) | Cod sursa (job #1419335)
#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 = p[k-1];}
}
}
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]<<' ';
}