Pagini recente » Cod sursa (job #1661020) | infoarena - comunitate informatica, concursuri de programare | Cod sursa (job #2873512) | Cod sursa (job #357357) | Cod sursa (job #1563485)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
char a[2000005]; int n;
char b[2000005]; int m;
int pi[2000005], nr;
vector<int> ret;
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s", &a); n = strlen(a);
scanf("%s", &b); m = strlen(b);
if(n > m) {cout << "0\n"; return 0;}
int k = 0;
for(int i = 1; i < n; i ++) {
while(k && a[i] != a[k]) k = pi[k];
if(a[i] == a[k]) k ++;
pi[i] = k;
}
k = 0;
for(int i = 0; i < m; i ++) {
while(k && b[i] != a[k]) k = pi[k];
if(b[i] == a[k]) k ++;
if(k == n) {
nr ++;
ret.push_back(i - k + 1);
k = pi[n - 1];
}
}
cout << nr << "\n";
for(int i = 0; i < ret.size() && i < 1000; i ++) cout << ret[i] << " ";
cout << "\n";
return 0;
}