Pagini recente » Cod sursa (job #265992) | Monitorul de evaluare | Atasamentele paginii Profil MadaPetrus | Monitorul de evaluare | Cod sursa (job #2417331)
#include <fstream>
#include <cstring>
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
const int Dim = 2e6 + 5;
char a[Dim], b[Dim];
int pi[Dim], pos[Dim];
int n, m, ans, k;
int main() {
f >> (a + 1) >> (b + 1);
n = strlen (a + 1);
m = strlen (b + 1);
for (int i = 2; i <= n; ++ i) {
while (k > 0 && a[k + 1] != a[i]) {
k = pi[k];
}
if (a[k + 1] == a[i]) {
++ k;
}
pi[i] = k;
}
k = 0;
for (int i = 2; i <= m; ++ i) {
while (k > 0 && a[k + 1] != b[i]) {
k = pi[k];
}
if (a[k + 1] == b[i]) {
++ k;
}
pos[i] = k;
}
for (int i = 1; i <= m; ++ i) {
if (pos[i] == n) ++ ans;
}
g << ans << '\n';
ans = 0;
for (int i = 1; i <= m; ++ i) {
if (pos[i] == n) {
g << i - n << " ";
++ ans;
}
if (ans == 1000)
return 0;
}
return 0;
}