Pagini recente » Cod sursa (job #2793297) | Cod sursa (job #1528216) | Monitorul de evaluare | Cod sursa (job #1678836) | Cod sursa (job #1305051)
#include <fstream>
#include <cstring>
const char IN [ ] = "strmatch.in";
const char OUT [] = "strmatch.out";
using namespace std;
const int kNMax = 2000200;
char P[kNMax], S[kNMax], x[2 * kNMax];
int pref[2 * kNMax];
int main()
{
ifstream fin(IN);
ofstream fout(OUT);
fin >> (P + 1) >> (S + 1);
int m = strlen(P + 1);
int n = strlen(S + 1);
for (int i = 1; i <= m; ++i)
x[i] = P[i];
int len = m;
x[++len] = '$';
for (int i = 1; i <= n; ++i)
x[++len] = S[i];
for (int i = 2; i <= len; ++i) {
int suf = pref[i - 1];
while (1) {
if (x[suf + 1] == x[i]) {
++suf;
break;
}
if (suf == 0)
break;
suf = pref[suf];
}
pref[i] = suf;
}
int res = 0;
for (int i = m + 2; i <= len; ++i)
if (pref[i] == m)
++res;
fout << res << "\n";
int cnt = 0;
for (int i = m + 2; cnt < 1000 && i <= len; ++i)
if (pref[i] == m) {
fout << i - m + 1 - (m + 1) - 1<< " ";
++cnt;
}
return 0;
}