Pagini recente » Cod sursa (job #1785206) | Cod sursa (job #1323636) | Cod sursa (job #1265894) | Cod sursa (job #337248) | Cod sursa (job #2933115)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
//ifstream fin("euclid3.in");
//ofstream fout("euclid3.out");
const int NMAX = 4e6;
int kmp[NMAX + 1];
string s;
void Kmp(){
kmp[1] = 0;
for(int i = 2; i <= (int)s.size() - 1; i++){
int l = kmp[i - 1];
while(l != 0 && s[l + 1] != s[i])
l = kmp[l];
if(s[l + 1] == s[i])
kmp[i] = l + 1;
}
}
int main(){
string s1, s2;
fin >> s1 >> s2;
s = "$" + s1 + s2;
Kmp();
int ans = 0;
for(int i = (int)s1.size() + 2; i <= (int)s.size() - 1; i++)
ans += (kmp[i] == (int)s1.size());
fout << ans << '\n';
int ind = 0;
for(int i = (int)s1.size() + 2; i <= (int)s.size() - 1; i++)
if(kmp[i] == (int)s1.size() && ind < 1000){
fout << i - 2 * (int)s1.size() << ' ', ++ind;
if(ind == 1000)
return 0;
}
return 0;
}