Pagini recente » Cod sursa (job #1771442) | Cod sursa (job #435529) | Cod sursa (job #2359591) | Cod sursa (job #491594) | Cod sursa (job #2879281)
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define dbg(x) cout << #x <<": " << x << "\n";
using ll = long long;
const string fn = "strmatch";
ifstream fin(fn + ".in");
ofstream fout(fn + ".out");
string t, pat;
vector<int> ans;
vector<int> prefix(string s){
vector<int> pi;
pi.resize((int)s.size());
for (int i = 1; i < (int)s.size(); ++i){
int j = pi[i - 1];
while(j > 0 && s[i] != s[j])
j = pi[j - 1];
if(s[i] == s[j])
j++;
pi[i] = j;
}
return pi;
}
int main(){
// ABA#CABBCABABAB
// 012345678901234
fin >> pat >> t;
vector<int> pi((int)pat.size());
string s = pat + "#" + t;
pi = prefix(s);
for (int i = pat.size() + 1; i < (int)s.size(); ++i)
if(pi[i] == (int)pat.size())
ans.pb(i - ((int)pat.size() + (int)pat.size()));
fout << ans.size() << '\n';
for(auto i : ans)
fout << i << " ";
return 0;
}