Pagini recente » Cod sursa (job #1251620) | Cod sursa (job #3288382) | Cod sursa (job #1945348) | Cod sursa (job #2424339) | Cod sursa (job #2347649)
#include <bits/stdc++.h>
#define nmax 2000005
using namespace std;
int N, M;
char B1[nmax], B2[nmax];
class Solution {
private:
inline vector<int> computePrefs(char A[]) {
int lg = strlen(A);
vector<int> pref(lg + 1);
return pref;
for (int i = 2; i <= lg; ++i) {
int left = pref[i - 1];
while(left > 0 && A[left] != A[i - 1]) {
left = pref[left];
}
if (A[left] == A[i-1]) {
pref[i] = left + 1;
}
}
return pref;
}
public:
inline void read() {
cin >> B1+1 >> B2+1;
}
inline void solve() {
vector<int>pref = computePrefs(B1 + 1);
int lg = strlen(B2 + 1);
int sol = 0;
vector<int> poz;
int p = 0;
for(int i = 1; i <= lg; ++i) {
while(p && B1[p+1] != B2[i]) {
p = pref[p];
}
if (B1[p+1] == B2[i]) {
p++;
}
if (p == strlen(B1+1)) {
sol++;
poz.push_back(i-strlen(B1+1));
p = pref[p];
}
}
cout << sol << "\n";
for(auto it: poz) {
cout << it << " ";
}
cout << "\n";
}
};
int main(){
int i;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
// ios::sync_with_stdio(false);
Solution sol;
sol.read();
sol.solve();
return 0;
}