Pagini recente » Cod sursa (job #1459941) | Cod sursa (job #2481852) | Cod sursa (job #656780) | Cod sursa (job #2034474) | Cod sursa (job #2174642)
#include <bits/stdc++.h>
using namespace std;
int p[2000001],n,m,maxx=-1,q[2000001],poz[1024];
string pat,txt;
void prefix()/// aici fac sirul p cu ajut caruia pot sa vad cate poz pot sa mut sirul cand gasesc un missmatch in kmp
/// verific care este lungimea prefixului care e si sufix in p[i]
{ memset(p,0,sizeof(p));
p[0]=0;
int i=1,j=0,k=0;;
for( i=1; i<m; ++i)
{
if(pat[i]==pat[j])
{
j++;
p[i]=j;
}
else
{
if(j!=0)
{j=p[j-1]; i--; }
else
{
p[i]=0;
}
}
// cout<<p[i]<<" ";
}
}
int k=0;
void KMP()
{
int i=0,j=0;
while(i<n){
if(txt[i]==pat[j])
{
i++;j++;
}
if(j==m)
{
q[k]=i-j;
k++;
j=p[j-1];
}
while(i<n && txt[i]!=pat[j])
{
if(j!=0)
j=p[j-1];
else
{
++i;
}
}
}
}
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f>>pat>>txt;
n=txt.size();
m=pat.size();
prefix();
KMP();
g<<k<<endl;;
if(k>1000)
for(int i=0;i<1000; ++i)
g<<q[i]<<" ";
else
for(int i=0;i<k; ++i)
g<<q[i]<<" ";
return 0;
}