Pagini recente » Cod sursa (job #2368854) | Cod sursa (job #2173394) | Cod sursa (job #2867903) | Cod sursa (job #887510) | Cod sursa (job #2339608)
#include <fstream>
#include <cstring>
int main(int argc, const char * argv[]) {
std::ifstream fin ("strmatch.in");
std::ofstream fout("strmatch.out");
char t[2000001], s[20000001];
int p[2000001], sol [1001];
fin >> (s + 1);
fin >> (t + 1);
int n = strlen(s + 1);
int m = strlen(t + 1);
int ap = 0;
//calculam p[i] - lungimea maxima a unui sufix terminat la pozitia care totodata este prefix al lui s
p[1] = 0;
int L = 0;
for (int i = 2; i <= n; ++i) {
//calculam P[i]
while (L != 0 && s[i] != s[L + 1]) {
L = p[L];
}
if (s[i] == s[L + 1]) {
L++;
}
p[i] = L;
}
L = 0;
for (int i = 1; i <= m; ++i) {
// voi testa potrivire a lui s in t care se termina la pozitia i
// semnificatia lui L la pasul i - lungimea maxima a unui sufix din t terminat la pozitia i
// care totodata este prefix de lungime L in s;
while (L != 0 && t[i] != s[L + 1]) {
L = p[L];
}
if (t[i] == s[L + 1]) {
L++;
}
if (L == n) {
// potrivire
ap++;
if(ap <= 1000) {
sol[ap] = L - n;
}
L = p[L]; // urmatoarea potrivire se poate suprapune cu cea curenta si o cautam extinzand cel mai lung prefix al intregului sir s
}
}
fout << ap << '\n';
for (int i = 1; i <= ap; ++i) {
fout << sol[i] << ' ';
}
return 0;
}