Pagini recente » Cod sursa (job #1555765) | Cod sursa (job #1692388) | Cod sursa (job #1065532) | Cod sursa (job #2138679) | Cod sursa (job #794226)
Cod sursa(job #794226)
#include <fstream>
#define L 2000001
#define N 1001
char A[L], B[L];
int pi[L];
int nRez, r[N];
inline void read() {
std::ifstream fin("strmatch.in");
fin >> A + 1 >> B + 1;
fin.close();
}
void solve() {
int q = 0, lenA = 1;
pi[1] = 0;
for (int i = 2; A[i] != '\0'; ++i, ++lenA) {
while (q && A[q + 1] != A[i])
q = pi[q];
if (A[q + 1] == A[i])
++q;
pi[i] = q;
}
q = 0;
for (int i = 1; B[i] != '\0'; ++i) {
while (q && A[q + 1] != B[i])
q = pi[q];
if (A[q + 1] == B[i])
++q;
if (q == lenA) {
++nRez;
if (nRez < 1000)
r[++r[0]] = i - lenA;
}
}
}
inline void print() {
std::ofstream fout("strmatch.out");
fout << nRez << '\n';
if (nRez != 0) {
fout << r[1];
for (int i = 2; i <= r[0]; ++i)
fout << ' ' << r[i];
fout << '\n';
}
fout.close();
}
int main() {
read();
solve();
print();
return 0;
}