Pagini recente » Cod sursa (job #1938437) | Cod sursa (job #939042) | Cod sursa (job #1485683) | Cod sursa (job #1805826) | Cod sursa (job #2269429)
#include <fstream>
#include <string>
#include <cstring>
#include <vector>
int* zFunction(std::string s)
{
int len = s.size();
int* zf = new int[len];
memset(zf, '\0', len * sizeof(int));
for(int i=1, l=0, r=0; i<len; i++)
{
if(i > r)
{
int j=i;
while(j < len && s[j-i] == s[j])j++;
zf[i] = j - i;
if(zf[i] > 0)
{
l = i;
r = j-1;
}
}
else
{
zf[i] = std::min(zf[i-l], r - i + 1);
int j = i + zf[i];
while(j < len && s[j-i] == s[j])j++;
zf[i] = j - i;
l = i;
r = j-1;
}
}
return zf;
}
int main()
{
std::string a,b;
std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");
fin>>a>>b;
b = a + b;
int* zf = zFunction(b);
std::vector<int> sol;
for(int i = a.size(); i < b.size(); i++)
if(zf[i] >= a.size())sol.push_back(i - a.size());
fout<<sol.size()<<'\n';
for(int i=0; i<std::min(1000, (int)sol.size()); i++)
fout<<sol[i]<<' ';
fout<<'\n';
}