Pagini recente » Cod sursa (job #526265) | Cod sursa (job #2664988) | Cod sursa (job #631957) | Cod sursa (job #934807) | Cod sursa (job #2721621)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
int zValue[4000005];
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int cnt = 0, n, m, left = 1, right = 1;
string pattern, text, str;
fin >> pattern >> text;
str = "$" + pattern + "&" + text;
n = str.size();
m = pattern.size();
for (int i = 1; i < n; ++i) {
zValue[i] = 0;
}
for (int i = 2; i < n; ++i) {
if (i > right) {
right = i;
while(right < n && str[right - left] == str[right]) {
zValue[i] += 1;
right += 1;
}
if (left + zValue[left] <= i + zValue[i]) {
left = i;
}
} else {
int k = i - left + 1;
if (i + zValue[k] < right) {
zValue[i] = zValue[k];
} else {
left = i - 1;
zValue[i] = right - i;
while (right < n && str[right - left] == str[right]) {
zValue[i] += 1;
right += 1;
}
if (left + zValue[left] <= i + zValue[i]) {
left = i;
}
}
}
}
for (int i = m + 2; i < n; ++i) {
if (zValue[i] == m) {
cnt += 1;
}
}
fout << cnt << "\n";
cnt = 0;
for (int i = m + 2; i < n; ++i) {
if (zValue[i] == m && cnt < 1000) {
cnt += 1;
fout << i - m - 2<< " ";
}
}
return 0;
}