Pagini recente » Cod sursa (job #7302) | Cod sursa (job #3201058) | Cod sursa (job #645879) | Cod sursa (job #1351214) | Cod sursa (job #1983340)
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define PI 3.141592653589793;
using namespace std;
int lps[4000005];
int result[1002];
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
string a, b;
getline(cin, a);
getline(cin, b);
int ind = 0, i = 1, j = 0, n = a.size(), m = b.size(), nr = 0;
while(i < n){
if(a[i] == a[ind]){
lps[i] = ind + 1;
i++;
ind++;
} else if(ind){
ind = lps[ind - 1];
} else {
i++;
}
}
i = 0;
while(i < m){
if(b[i] == a[j]) {
i++;
j++;
} else if(j){
j = lps[j - 1];
} else {
i++;
}
if(j == a.size()){
nr++;
j = lps[j-1];
if(nr <= 1000)
result[nr] = i - n;
}
}
printf("%d\n", nr);
for(int i=1; i <= min(nr, 1000); i++)
printf("%d ", result[i]);
}