Pagini recente » Cod sursa (job #2405761) | Cod sursa (job #2364726) | Cod sursa (job #209792) | Cod sursa (job #1839934) | Cod sursa (job #1161467)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
string s,s1,s2;
vector <int> r;
int center,dr,i,dr2,coresp,z[4000015],equiv;
int main(void)
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f>>s1>>s2;
s=s1+"*"+s2;
for (i=1;i<s.size();i++)
{
if (i>=dr)
{
center=i;
dr=i;
coresp=0;
while (s[dr]==s[coresp])
{
dr++;
coresp++;
}
z[i]=coresp;
}
else
{
equiv=i-center;
dr2=i+z[equiv];
if (dr2>=dr)
{
center=i;
coresp=dr-center;
while (s[dr]==s[coresp])
{
dr++;
coresp++;
}
z[i]=coresp;
}
else
z[i]=dr2-i;
}
if (z[i]==s1.size())
r.push_back(i-s1.size()-1);
}
g<<r.size()<<'\n';
for (i=0;(i<r.size())&&(i<1000);i++)
g<<r[i]<<' ';
g<<'\n';
return 0;
}