Pagini recente » Cod sursa (job #1610681) | Cod sursa (job #2284860) | Cod sursa (job #855634) | Cod sursa (job #764842) | Cod sursa (job #1171978)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
#define nmax 2000005
long n, m;
int i, j;
int overlap[nmax];
vector <int> sol;
string pattern, text;
void pp(){
i = 0;
overlap[0] = overlap[1] = 0;
for (j = 2; j <= m; j++){
i = overlap[j-1];
while (1){
if (pattern[j-1] == pattern[i]){
overlap[j] = i + 1;
break;
} else if (i == 0) {
overlap[j] = 0;
break;
}
i = overlap[i];
}
}
}
void kmp(){
j = 0;
i = 0;
while (i <= n)
if (text[i] == pattern[j]){
i++;
j++;
if (j == m) sol.push_back(i-m);
} else if (j > 0) j = overlap[j];
else i++;
}
int main(){
ifstream in("strmatch.in");
ofstream out("strmatch.out");
getline(in, pattern);
getline(in, text);
n = text.size();
m = pattern.size();
pp();
kmp();
int g;
if (sol.size() < 1000)
g = sol.size();
else g = 1000;
out << g << "\n";
for (i=0; i<g; i++)
out << sol[i] << " ";
out << "\n";
return 0;
}