Pagini recente » Cod sursa (job #2215049) | Cod sursa (job #2184880) | Cod sursa (job #1635525) | Cod sursa (job #678386) | Cod sursa (job #2066799)
#include <bits/stdc++.h>
using namespace std;
#define MAXLEN 2000003
char s[MAXLEN], p[MAXLEN];
int pref[MAXLEN];
int n, m;
void buildPref() {
int i = 0, j = -1;
pref[0] = -1;
while (i < m) {
while (j >= 0 && p[i] != p[j])
j = pref[j];
i++, j++;
pref[i] = j;
}
}
vector<int> strMatch() {
vector<int> sol;
int i = 0, j = 0;
while (i < n) {
while (j >= 0 && s[i] != p[j])
j = pref[j];
i++, j++;
if (j == m) {
j = pref[j];
sol.push_back(i - m);
}
}
return sol;
}
void read() {
scanf("%s %s ", p, s);
n = strlen(s);
m = strlen(p);
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
read();
buildPref();
auto result = strMatch();
printf("%d\n", result.size());
for(int item: result)
printf("%d ", item);
return 0;
}