Pagini recente » Cod sursa (job #2390975) | Cod sursa (job #2254306) | Cod sursa (job #1947117) | Cod sursa (job #836895) | Cod sursa (job #1645195)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
char a[2000005]; int na;
char b[2000005]; int nb;
vector<int> ans; int nr = 0;
int pi[2000005];
void prefix() {
int k = 0; pi[1] = 0;
for(int i = 2; i <= na; i ++) {
while(k && a[i] != a[k + 1]) k = pi[k];
if(a[i] == a[k + 1]) k ++;
pi[i] = k;
}
}
void caut() {
int k = 0;
for(int i = 1; i <= nb; i ++) {
while(k && b[i] != a[k + 1]) k = pi[k];
if(b[i] == a[k + 1]) k ++;
if(k == na) {
if(ans.size() > 999) nr ++;
else nr ++, ans.push_back(i - na);
k = pi[na];
}
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
gets(a + 1); gets(b + 1);
na = strlen(a + 1);
nb = strlen(b + 1);
prefix();
caut();
cout << nr << "\n";
for(int i = 0; i < ans.size(); i ++) cout << ans[i] << " ";
cout << "\n";
return 0;
}