Pagini recente » Cod sursa (job #214490) | Cod sursa (job #2896573) | Cod sursa (job #2974298) | Cod sursa (job #2566156) | Cod sursa (job #3243782)
#include <fstream>
#include <iostream>
#define NMAX 2000002
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int z[NMAX], N;
void strmatch(string str) {
N = str.length();
long l, r;
l = r = 0;
for (long i = 1; i < N; ++i) {
if (i > r) {
long j = 0;
r = l = i;
while (r < N && str[j] == str[r]) {
j++;
r++;
}
r--;
z[i] = r - l + 1;
}
else {
long k = i - l;
if (z[k] < r - i) {
z[i] = z[k];
}
else {
long j = r - i;
l = i;
while (r < N && str[j] == str[r]) {
j++;
r++;
}
r--;
z[i] = r - l + 1;
}
}
}
}
int main()
{
string word, s;
f >> word >> s;
long len = word.length(), con = 0, nr = 0;
strmatch(word + "?" + s);
for (long i = len; i < N; ++i) {
if (z[i] == len) {
con++;
}
}
g << con << "\n";
for (long i = len; i < N; ++i) {
if (z[i] == len) {
g << i - len - 1 << " ";
nr++;
}
if (nr >= 1000)
break;
}
return 0;
}