Pagini recente » Cod sursa (job #1166031) | Cod sursa (job #1926072) | Cod sursa (job #1410868) | Cod sursa (job #1363677) | Cod sursa (job #3030643)
#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);
j=0;
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<<" ";
}
}