Pagini recente » Cod sursa (job #2168203) | Cod sursa (job #478189) | Cod sursa (job #275208) | Cod sursa (job #858510) | Cod sursa (job #2883143)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
using ll = long long;
const int NMAX(2000005);
int pi[NMAX];
char a[NMAX], b[NMAX];
int main()
{
fin >> (a + 1) >> (b + 1);
int n = strlen(a + 1), m = strlen(b + 1);
int k = 0;
for(int i = 2; i <= n; ++i){
while(k > 0 && a[i] != a[k + 1])
k = pi[k];
if(a[i] == a[k + 1])
++k;
pi[i] = k;
}
vector<int> vec;
k = 0;
for(int i = 1; i <= m; ++i){
while(k > 0 && b[i] != a[k + 1])
k = pi[k];
if(b[i] == a[k + 1])
++k;
if(k == n){
vec.push_back(i - n);
k = pi[k];
}
}
fout << vec.size() << '\n';
for(int i = 0; i < min((int)vec.size(), 1000); ++i)
fout << vec[i] << ' ';
return 0;
}