Pagini recente » Cod sursa (job #2887072) | Cod sursa (job #184440) | Cod sursa (job #1531092) | Cod sursa (job #193072) | Cod sursa (job #2108340)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string pattern, text;
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;
int i=0,j=0;
for(;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++;
}
}
if(j==pat.size())
{
sol.push_back(i-pat.size());
}
return sol;
}
int main()
{
fin>>pattern>>text;
vector<int> sol = kmp(pattern, text);
fout<<sol.size()<<'\n';
for(auto q:sol)
{
fout<<q<<' ';
}
return 0;
}