Pagini recente » Cod sursa (job #3208037) | Cod sursa (job #3159151) | Cod sursa (job #2695660) | Cod sursa (job #1845528) | Cod sursa (job #2976161)
#include <bits/stdc++.h>
using namespace std;
vector <int> ComputePI(string s){
int n = s.size();
vector <int> pi(n);
pi[0] = 0;
for (int i = 1; i < n; i++){
pi[i] = 0;
int j = pi[i - 1];
for (; j; j = pi[j - 1]){
if (s[i] == s[j]){
pi[i] = j + 1;
break;
}
}
if (j == 0 && s[0] == s[i])
pi[i] = 1;
}
return pi;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string s, t;
cin >> s >> t;
auto pi = ComputePI(s + "#");
int last = 0, ans = 0;
int LIM = 1000;
vector <int> sol;
int n = s.size();
int m = t.size();
for (int i = 0; i < m; i++){
int curr = 0;
int j = last;
for (; j; j = pi[j - 1]){
if (t[i] == s[j]){
curr = j + 1;
break;
}
}
if (j == 0 && s[0] == t[i])
curr = 1;
if (curr == n){
ans++;
if (LIM > 0){
sol.push_back(i - n + 1);
LIM--;
}
}
last = curr;
}
cout << ans << '\n';
for (int it: sol)
cout << it << ' ';
return 0;
}