Pagini recente » Cod sursa (job #2662495) | Cod sursa (job #1061149) | Cod sursa (job #2608864) | Cod sursa (job #147155) | Cod sursa (job #1419444)
#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) 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<<sol.size()<<'\n';
for (int i = 0; i < sol.size(); i++)
g<<sol[i]<<' ';
}