Pagini recente » Cod sursa (job #2096198) | Cod sursa (job #2699729) | Cod sursa (job #944597) | Cod sursa (job #707761) | Cod sursa (job #2347638)
#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 = 1;
for(int i = 1; i <= lg; ++i) {
if (B2[i] == B1[p]) {
p++;
if(p-1 == strlen(B1 + 1)) {
sol++;
poz.push_back(i-p+1);
p = pref[p-1] + 2;
}
continue;
}
while(p > 0 && B2[i] != B1[p]) {
p = pref[p];
}
if(p == 0) {
p = 1;
}
if (p > 0 && B2[i] == B1[p]) {
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;
}