Pagini recente » Cod sursa (job #2621828) | Cod sursa (job #641626) | Cod sursa (job #1195178) | Cod sursa (job #2804128) | Cod sursa (job #1419358)
#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[1] = 0;
for (i = 2; i < n; i++)
{
while(k && a[k+1] != a[i]) k = p[k];
if (a[k+1] == a[i]) k++;
p[i] = k;
}
}
void kmp()
{
int k, i;
int n = a.size(), m = b.size();
k = 0;
for (i = 1; i < m; i++)
{
while (k && a[k+1]!=b[i]) k = p[k];
if (a[k+1] == b[i]) k++;
if (k == n - 1 && nsol < 1000) sol[nsol++] = i - n + 1;
}
}
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f>>a>>b;
string c;
c = "0"; c+=a; a = c;
c = "0"; c+=b; b = c;
prefix();
kmp();
g<<nsol<<'\n';
for (int i = 0; i < nsol && i < 1000; i++)
g<<sol[i]<<' ';
}