Pagini recente » Cod sursa (job #244674) | Cod sursa (job #3232940) | Cod sursa (job #1500821) | Cod sursa (job #2187196) | Cod sursa (job #2154919)
#include <fstream>
#include <cstring>
#define DEF 2000010
#define DEFS 1010
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
char s[DEF], t[DEF];
int n, m, L, P[DEF], sol, Sol[DEFS];
/// Caut o aparitie a lui t in s
/// m = lungimea lui t
/// n = lungimea lui s
int main () {
fin >> t + 1 >> s + 1;
m = strlen (t + 1);
n = strlen (s + 1);
for (int i = 2; i <= m; ++ i) {
while (L != 0 and t[i] != t[L + 1]) {
L = P[L];
}
if (t[i] == t[L + 1]) {
++ L;
}
P[i] = L;
}
L = 0;
for (int i = 1; i <= n; ++ i) {
while (L != 0 and s[i] != t[L + 1]) {
L = P[L];
}
if (s[i] == t[L + 1]) {
++ L;
}
if (L == m) {
++ sol;
if (sol <= 1000)
Sol[sol] = i - m;
L = P[L];
}
}
fout << sol << "\n";
sol = min (sol, 1000);
for (int i = 1; i <= sol; ++ i) {
fout << Sol[i] << " ";
}
return 0;
}