Pagini recente » Cod sursa (job #2097400) | Cod sursa (job #2972738) | Cod sursa (job #91819) | Cod sursa (job #525704) | Cod sursa (job #3030047)
#include<iostream>
#include<fstream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string s,b;
vector<int> v;
const int NMAX=4000007;
int i,j,patsiz,maxpros;
int z[NMAX];
int main()
{
in>>s>>b;
patsiz=s.size();
s.push_back('*');
s.append(b);
maxpros=0;
for(i=1;i<s.size();i++)
{
j=min(z[i],maxpros-i+1);
while(s[j]==s[j+i]&&j+i<s.size())
{
z[i+j]=z[j];
j++;
}
maxpros=max(maxpros,j+i);
z[i]=j;
if(z[i]==patsiz)
{
v.push_back(i);
}
if(v.size()==1000)
{
break;
}
}
out<<v.size()<<"\n";
for(auto w:v)
{
out<<w-patsiz-1<<" ";
}
}