Pagini recente » Cod sursa (job #2562679) | Cod sursa (job #172276) | Cod sursa (job #2267718) | Cod sursa (job #2857553) | Cod sursa (job #1974328)
#include <bits/stdc++.h>
using namespace std;
const int Nmax = 2000005;
char A[Nmax], B[Nmax];
int N, M;
int Pref[Nmax];
void make_prefix()
{
int p = 0;
for(int i = 2; i <= M; ++i) {
while(p && B[i] != B[p + 1])
p = Pref[p];
p += (B[p + 1] == B[i]);
Pref[i] = p;
}
}
void make_match()
{
vector<int> sol;
int cnt = 0;
int p = 0;
for(int i = 1; i <= N; ++i) {
while(p && A[i] != B[p + 1])
p = Pref[p];
p += (B[p+1] == A[i]);
if(p == M) {
++cnt;
if(sol.size() < 1000) {
sol.push_back(i - M);
}
p = Pref[p];
}
}
cout << cnt << "\n";
for(auto it : sol)
cout << it << " ";
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
ios::sync_with_stdio(false);
cin >> (B+1);
cin >> (A+1);
A[0] = '#';
B[0] = '#';
N = strlen(A + 1);
M = strlen(B + 1);
make_prefix();
make_match();
return 0;
}