Pagini recente » Cod sursa (job #3350419) | Cod sursa (job #3314622) | Cod sursa (job #3353331) | Cod sursa (job #3314003) | Cod sursa (job #3321070)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <climits>
std::ifstream f("strmatch.in");
std::ofstream g("strmatch.out");
using namespace std;
typedef long long int ll;
const int nMax = 2e6 + 5;
int lps[nMax], rez[nMax], nrr;
string s, t;
void prefixsufix(string s)
{
int m = s.size(), lg = 0;
int i = 1;
while(i < m){
if (s[i] == s[lg])lg++,lps[i] = lg,i++;
else if (lg != 0)lg = lps[lg-1];
else lps[i++] = 0;
}
}
void KMP(string t,string s)
{
int n = t.size(), m = s.size();
int lg = 0, i = 0;
while(i < n){
if (t[i] == s[lg]){
lg++,i++;
if (lg == m)rez[++nrr] = i - m,lg = lps[lg-1];
}
else if (lg != 0)lg = lps[lg-1];
else i++;
}
}
void solve()
{
prefixsufix(s);
KMP(t,s);
g << nrr << '\n';
for (int it = 1;it <= min(1000,nrr);it++)g << rez[it] << " ";
}
int main()
{
getline(f,s);
getline(f,t);
solve();
}