Pagini recente » Cod sursa (job #2613400) | Cod sursa (job #2744647) | Cod sursa (job #2275077) | Cod sursa (job #882467) | Cod sursa (job #2027400)
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#define MAX 2000005
#define NMAX 1000
using namespace std;
string a, b;
int nr, p[MAX];
vector<int> apps;
void prefix() {
p[0] = -1;
int k = -1;
for(int i = 1; i < a.size(); ++i) {
if(a[i] == a[k + 1])
++k;
else
while(k >= 0 && a[i] != a[k + 1])
k = p[k];
p[i] = k;
}
}
void kmp() {
prefix();
int k = -1;
for(int i = 0; i < b.size(); ++i) {
while(k >= 0 && a[k + 1] != b[i])
k = p[k];
if(a[k + 1] == b[i])
++k;
if(k == a.size() - 1) {
++nr;
if(nr <= NMAX)
apps.push_back(i - a.size() + 1);
}
}
}
int main() {
ifstream f("strmatch.in");
ofstream g("strmatch.out");
getline(f, a);
getline(f, b);
kmp();
g << nr << "\n";
for(int i = 0; i < apps.size(); ++i)
g << apps[i] << " ";
return 0;
}