Pagini recente » Cod sursa (job #1046709) | Cod sursa (job #2309319) | Cod sursa (job #1551499) | Cod sursa (job #1398903) | Cod sursa (job #2575760)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string txt, pat;
vector<int> v;
int lps[2000005];
void computeLPS()
{
int len = 0, i = 1;
while(i < pat.size())
{
if(pat[i] == pat[len])
{
len++;
lps[i] = len;
i++;
}
else
{
if(len)
{
len = lps[len-1];
}
else
{
i++;
}
}
}
}
int nr;
void KMP()
{
computeLPS();
int i, j;
i = j = 0;
while(i < txt.size())
{
if(txt[i] == pat[j])
{
i++;
j++;
}
else
{
if(j)
{
j = lps[j-1];
}
else
{
i++;
}
}
if(j == pat.size())
{
nr++;
if(nr < 1000)
{
v.push_back(i-j);
}
j = lps[j-1];
}
}
}
int main()
{
fin>>pat>>txt;
KMP();
fout<<nr<<'\n';
for(int el : v)
{
fout<<el<<' ';
}
fin.close();
fout.close();
return 0;
}