Pagini recente » Cod sursa (job #1097531) | Cod sursa (job #2313324) | Cod sursa (job #2215712) | 1000101-1 | Cod sursa (job #1139675)
//Z-Algorithm
#include <fstream>
#include <vector>
#include <string>
using namespace std;
const int N=2000005;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b, c;
int Z[2*N];
int main()
{
int i, R, L, k;
vector <int> sol;
fin>>a>>b;
c=a+b;
R=L=0;
Z[0]=c.size();
for(i=1;i<c.size();i++)
{
if(i>R)
{
L=R=i;
while(R<c.size()&&c[R]==c[R-L]) R++;
Z[i]=R-L;
R--;
}
else
{
k=i-L;
if(Z[k]<R-i+1) Z[i]=Z[k];
else
{
L=i;
while(R<c.size()&&c[R]==c[R-L]) R++;
Z[i]=R-L;
R--;
}
}
if(i>=a.size()&&Z[i]>=a.size()&&sol.size()<1000) sol.push_back(i-a.size());
}
fout<<sol.size()<<"\n";
for(i=0;i<sol.size();i++) fout<<sol[i]<<" ";
}