Pagini recente » Istoria paginii utilizator/patrascu_vlad_323ca | Istoria paginii utilizator/mariapopescu2907 | Diferente pentru olimpici intre reviziile 175 si 180 | Istoria paginii utilizator/ransaked | Cod sursa (job #2040232)
#include <fstream>
#include <string>
using namespace std;
ofstream fout("strmatch.out");
ifstream fin("strmatch.in");
string s;
string s1;
int n;
int n1;
int l[2000010];
int a;
int sol[1010];
void makeSufix(){
l[0] = 0;
int k = -1;
for(int i = 1; i < n; i++){
k = l[i - 1] - 1;
while(s[k + 1] != s[i] && k > -1)
k = l[k] - 1;
if(s[k + 1] == s[i]){
k++;
}
l[i] = k + 1;
}
}
void kmp(){
int k = -1;
for(int i = 0; i < n1; i++){
while(s[k + 1] != s1[i] && k > -1)
k = l[k] - 1;
if(s[k + 1] == s1[i]){
k++;
}
if(k == n - 1){
if(a <= 1000) sol[++a] = i - n + 1;
else a++;
k = l[k] - 1;
}
}
fout << a << '\n';
for(int i = 1; i <= min(a,1000); i++){
fout << sol[i] << ' ';
}
}
int main()
{
fin >> s;
n = s.size();
fin >> s1;
n1 = s1.size();
makeSufix();
kmp();
return 0;
}