Pagini recente » Cod sursa (job #1352197) | Cod sursa (job #2888487) | Cod sursa (job #1663810) | Cod sursa (job #1421849) | Cod sursa (job #2800689)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
vector <int> KMP(string s){
s = "$" + s;
vector <int> pi(s.size());
int k = 0;
for (int i = 2; i < (int) s.size(); ++ i){
while (k && s[i] != s[k + 1])
k = pi[k];
if (s[i] == s[k + 1])
k ++;
pi[i] = k;
}
pi.erase(pi.begin());
return pi;
}
vector <int> GasestePotriviri(string s, string t){
vector <int> kmp = KMP(s + '$' + t);
vector <int> sol;
for (int i = (int) s.size() + 1; i < (int) kmp.size(); ++ i)
if (kmp[i] == (int) s.size())
sol.push_back(i - (2 * (int) s.size()));
/*
* S = "abab"
* T = "ababcababab"
* S + '$' + T = abab$ababcababab
*/
return sol;
}
int main(){
string s, t;
fin >> s >> t;
vector <int> sol = GasestePotriviri(s, t);
int n = (int) sol.size();
fout << n << '\n';
if(n > 1000)
n = 1000;
for (int i = 0; i < n; ++ i)
fout << sol[i] << ' ';
return 0;
}