Pagini recente » Cod sursa (job #295132) | Cod sursa (job #2169220) | Cod sursa (job #865965) | Cod sursa (job #630798) | Cod sursa (job #1428118)
#include <iostream>
#include <fstream>
#include <vector>
#define MAXA 4000000
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n, x = -1, kmp[MAXA];
string a, b;
vector<int> sol;
int main() {
int i;
f >> a >> b;
n = a.length();
a += b;
kmp[0] = -1;
for(i = 1; i < a.length() && sol.size() < 1000; i++) {
while(x >= 0 && a[i] != a[x + 1]) x = kmp[x];
if(a[i] == a[x + 1]) x++;
kmp[i] = x;
if(x >= n - 1 && i >= 2 * n - 1)
sol.push_back(i - 2 * n + 1);
}
g << sol.size() << '\n';
for(i = 0; i < sol.size(); i++)
g << sol[i] << ' ';
g << '\n';
return 0;
}