Pagini recente » Cod sursa (job #2418580) | Profil Diana69 | Cod sursa (job #1021949) | Cod sursa (job #918881) | Cod sursa (job #2154900)
#include <fstream>
#include <cstring>
#include <vector>
#define DEF 2000010
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
char s[DEF], t[DEF];
int n, m, L, P[DEF];
vector < int > Sol;
/// 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.push_back (i - m);
L = P[L];
}
}
fout << Sol.size () << "\n";
for (int i = 0; i < Sol.size (); ++ i) {
fout << Sol[i] << " ";
}
return 0;
}