Pagini recente » Cod sursa (job #2628138) | Clasamentul arhivei de probleme | Cod sursa (job #1225207) | Cod sursa (job #945407) | Cod sursa (job #1419446)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
#define maxn 2000007
int p[maxn], nsol;
string a, b;
vector<int> sol;
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++;
if (nsol < 1000) sol.push_back(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 < sol.size(); i++)
g<<sol[i]<<' ';
}