Pagini recente » Borderou de evaluare (job #1010402) | Cod sursa (job #550561) | Cod sursa (job #209173) | Cod sursa (job #449501) | Cod sursa (job #1144910)
#include<string>
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string s1,s2;
int sar[2000005],n1,n2,nr;
vector<int> sol;
void completeaza()
{
for(int i=2;i<=n1;i++)
if(s1[i-1]==s1[sar[i-1]])
sar[i]=sar[i-1]+1;
else if(s1[i-1]==s1[0]) sar[i]=1;
}
void kmp()
{
int i,j,k=0,nrap=0;
for(i=0;i<n2;)
{
j=0;k=i;
while(j<n1&&s2[k]==s1[j]){k++;j++;}
if(j==n1)sol.push_back(i);
i=k-sar[j];
}
nr=sol.size();
g<<nr<<'\n';
nrap=min(1000,nr);
for(i=0;i<nrap;i++)
g<<sol[i]<<" ";
}
int main()
{
sar[0]=-1;sar[1]=0;
f>>s1>>s2;
n1=s1.size();
n2=s2.size();
completeaza();
kmp();
return 0;
}