Pagini recente » Profil Filimon_Theodor | Cod sursa (job #1404980) | Cod sursa (job #577684) | Cod sursa (job #309994) | Cod sursa (job #2454386)
#include<bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
string s1, s2;
int poz = 1, ind;
int lps [2000003];
vector <int> ans;
int main (){
fin >> s1 >> s2;
while (poz < s1.size ()){
if (s1 [poz] == s1 [ind])
lps [poz ++] = ++ ind;
else{
if (ind)ind = lps [ind - 1];
else lps [poz ++] = 0;
}
}
poz = 0;
while (poz < s2.size ()){
if (s1 [ind] == s2 [poz])
poz ++, ind ++;
if (ind == s1.size ()){
ans.push_back (poz - ind);
ind = lps [ind - 1];
}
else if (poz < s2.size () && s1 [ind] != s2 [poz]){
if (ind)ind = lps [ind - 1];
else poz ++;
}
}
fout << ans.size () << '\n';
for (int poz = 0; poz < min ((int)ans.size (), 1000); poz ++)
fout << ans [poz] << " ";
return 0;
}