Pagini recente » Cod sursa (job #2366411) | Cod sursa (job #394541) | Cod sursa (job #1366638) | Cod sursa (job #897699) | Cod sursa (job #803798)
Cod sursa(job #803798)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
const int N = 2000005;
char pattern[N], text[N];
int Z[N], match[N];
ifstream in("strmatch.in");
ofstream out("strmatch.out");
void strmatch(){
int best = 0;
for (int i = 2 ; pattern[i] ; i++){
if (i <= best + Z[best])
Z[i] = min(best + Z[best] - i, Z[2 * best - i]);
while (pattern[i + Z[i]] == pattern[Z[i] + 1])
++Z[i];
if (best + Z[best] < i + Z[i])
best = i;
}
best = 0;
for (int i = 1 ; text[i] ; i++){
if (i <= best + match[best])
match[i] = min(best + match[best] - i, Z[i - best + 1]);
while (text[i + match[i]] == pattern[match[i] + 1])
++match[i];
if (best + match[best] < i + match[i])
best = i;
}
}
int main(){
vector<int> v;
in >> pattern + 1 >> text + 1;
strmatch();
int Q = strlen(pattern + 1);
for (int i = 1 ; text[i] ; i++)
if (match[i] >= Q)
v.push_back(i);
out << v.size() << "\n";
if (v.size() > 1000)
v.resize(1000);
for (vector<int> :: iterator it = v.begin() ; it != v.end() ; it++)
out << (*it) - 1 << " ";
out << "\n";
return 0;
}