Pagini recente » Cod sursa (job #2435652) | Cod sursa (job #2656749) | Cod sursa (job #52147) | Cod sursa (job #2857893) | Cod sursa (job #2904872)
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#define MAX 2000005
using namespace std;
int f[MAX];
vector<int> ans;
void compute_table(string b, int n){
int k;
for(int i = 1; i <= n - 1; ++i){
k = f[i - 1];
while(k != 0 && b[i] != b[k])
k = f[k - 1];
if(b[i] == b[k])
k += 1;
f[i] = k;
}
}
int kmp(string a, string b, int m, int n){
int p = 0, count = 0;
for(int i = 0; i < m; ++i){
while(p == n || (p != 0 && a[i] != b[p]))
p = f[p - 1];
if(a[i] == b[p])
p += 1;
if(p == n){
ans.push_back(i + 1 - n);
++count;
}
}
return count;
}
int main(){
ifstream fin;
ofstream fout;
fin.open("strmatch.in");
fout.open("strmatch.out");
string a, b;
int m, n;
getline(fin, b);
getline(fin, a);
n = b.size();
m = a.size();
compute_table(b, n);
fout << kmp(a, b, m, n) << "\n";
for(int i = 0; i < 1000; ++i)
fout << ans[i] << " ";
}