Pagini recente » Cod sursa (job #2537898) | Cod sursa (job #2366437) | Cod sursa (job #674775) | Cod sursa (job #1655929) | Cod sursa (job #2880180)
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int cnt;
string s, patt;
int lcs[2000005];
vector <int> ans;
void precalc()
{
int i = 1, j = 0;
lcs[0] = 0;
while(i < patt.size()){
if(patt[i] == patt[j]){
j++;
lcs[i] = j;
i++;
}
else{
if(j)
j = lcs[j - 1];
else
lcs[i] = 0, i++;
}
}
}
void kmp()
{
int i = 0, j = 0;
while(i < s.size()){
if(patt[j] == s[i])
++i, ++j;
if(j == patt.size()){
ans.push_back(i - j);
j = lcs[j - 1];
}
else if(i < s.size() and patt[j] != s[i]){
if(j)
j = lcs[j - 1];
else
i++;
}
}
}
int main()
{
int n, i, j;
cin >> patt >> s;
precalc();
kmp();
cout << ans.size() << "\n";
int x = ans.size();
for(i = 0; i < min(1000, x); i++)
cout << ans[i] << " ";
//for(i = 0; i < patt.size(); i++)
//cout << precalc[i] << " ";
return 0;
}