Pagini recente » Cod sursa (job #164841) | Cod sursa (job #631391) | Cod sursa (job #1440658) | Cod sursa (job #1941454) | Cod sursa (job #2108337)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int* precalc(const string& pat)
{
int* lps = new int [pat.size()];
lps[0]=0;
for(int i=1;i<pat.size();i++)
{
if(pat[i]==pat[lps[i-1]])
{
lps[i]=lps[i-1]+1;
}
else
{
lps[i]=0;
}
}
return lps;
}
vector<int> kmp(const string& pat, const string& txt)
{
int* lps = precalc(pat);
vector<int> sol;
for(int i=0,j=0;i<txt.size();)
{
if(j==0 && pat[j] != txt[i])
{
i++;
continue;
}
if(j==pat.size())
{
sol.push_back(i-pat.size());
j=lps[j-1];
continue;
}
if(pat[j] != txt[i])
{
j = lps[j-1];
continue;
}
if(pat[j] == txt[i])
{
i++;
j++;
}
}
return sol;
}
int main()
{
string pat,txt;
fin>>pat>>txt;
vector<int> sol = kmp(pat, txt);
fout<<sol.size()<<'\n';
for(auto q:sol)
{
fout<<q<<' ';
}
return 0;
}