Pagini recente » Cod sursa (job #406621) | Cod sursa (job #3219558) | Cod sursa (job #2867729) | Cod sursa (job #1057032) | Cod sursa (job #940909)
Cod sursa(job #940909)
// Potrivirea sirurilor KMP
#include <cstdio>
#include <vector>
#include <string>
#include <iostream>
#include <fstream>
#define SIZE 2000001
using namespace std;
string A, B;
int T[SIZE];
void process_word(string &A) {
int s = A.size();
T[0] = -1;
T[1] = 0;
int pos = 2, cnd = 0;
while(pos < s) {
if (A[cnd] == A[pos - 1]) {cnd++; T[pos] = cnd; pos++;}
else if(cnd > 0) {cnd = T[cnd];}
else {T[pos] = 0; pos++;}
}
/*
for(int i = 0; i < s; i++) cout << T[i] << ' ';
cout << endl; */
}
int main()
{
//freopen("strmatch.in", "r", stdin);
//freopen("strmatch.out", "w", stdout);
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
getline(fin, A);
getline(fin, B);
//cout << A << endl << B << endl;
process_word(A);
vector<int> found;
int sa = A.size();
int sb = B.size();
int count = 0;
int m = 0, i = 0;
while(m + sa <= sb && count < 1000) {
while(i < sa && A[i] == B[m + i]) i++;
if (i == sa) {found.push_back(m);
//cout << m << endl;
count++;
m = m + i - 1 - T[sa - 1];
i = T[sa - 1]; }
else {m = m + i - T[i]; if(i) i = T[i];}
}
fout << count << endl;
if (count) fout << found[0];
for(int j = 1; j < found.size(); j++)
fout << ' ' << found[j];
fout << endl;
return 0;
}