Pagini recente » Cod sursa (job #2956696) | Cod sursa (job #2384487) | Cod sursa (job #2116202) | Cod sursa (job #802930) | Cod sursa (job #1412434)
#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>
using namespace std;
const int maxn = 100005;
char a[maxn], b[maxn];
int pi[maxn];
inline vector <int> kmp(char *a, char *b, int *pi) { /// searches for A in B
vector <int> matches;
int k = 0;
int n = strlen(a + 1);
int m = strlen(b + 1);
for(int i = 2 ; i <= n ; ++ i) {
while(k != 0 && a[k + 1] != a[i])
k = pi[k];
if(a[k + 1] == a[i])
++ k;
pi[i] = k;
}
k = 0;
for(int i = 1 ; i <= m ; ++ i) {
while(k != 0 && a[k + 1] != b[i])
k = pi[k];
if(a[k + 1] == b[i])
++ k;
if(k == n) {
matches.push_back(i - n);
k = pi[k];
}
}
return matches;
}
int main() {
ifstream fin("kmp.in");
ofstream fout("kmp.out");
fin.getline(a + 1, maxn);
fin.getline(b + 1, maxn);
vector <int> matches = kmp(a, b, pi);
fout << matches.size() << '\n';
for(int i = 0 ; i < min(1000, int(matches.size())) ; ++ i)
fout << matches[i] << ' ';
}