Pagini recente » Cod sursa (job #2723041) | Cod sursa (job #2752278) | Cod sursa (job #1580494) | Cod sursa (job #73352) | Cod sursa (job #1741612)
#include <iostream>
#include <string.h>
#include <fstream>
char w[2000002];
char s[2000002];
int match [2000002], sl, wl, potriviri[1002];
using namespace std;
void kmp_match()
{
match [0]=0;
int j = 0;
for (int i = 1; i < wl; i++)
{
while (j > 0 && (w[j] != w[i]))
j = match[j-1];
if (w[j] == w[i])
j++;
match[i] = j;
}
}
int main ()
{
int nr, i=0, m=0, j=0, x=0;
ifstream input ("strmatch.in");
ofstream output ("strmatch.out");
input>>w;
input>>s;
wl=strlen (w);
sl=strlen (s);
kmp_match(); ///calculam tabela
//for(i=0;i<=wl;++i)
// cout<<w[i]<<" ";
//cout<<endl;
//for(i=0;i<wl;++i)
// cout<<match[i]<<" ";
//cout<<endl;
///cautam propriu zis
while (m+i<sl)
{
if(w[i]==s[m+i])
{
if(i==wl-1)
{
++x;
if(j<1000)
{
potriviri[j]=m;
++j;
}
}
++i;
}
else
{
if(i!=0) ///nu cautam primu caracter ca ala nici n-are pref/suf
{
m+=i - match[i-1];
i=match[i-1];
}
else
{
++m;
}
}
}
/// asta nu mere da-l undeva
/*for (i=0;i<sl;++i)
{
cout<<x<<" ";
while (x>0 && w[x+1]!=s[i])
x=match[x];
if(w[x+1]==s[i]) ++x; ///avem o potrivire
if(x==wl-1)
{
if(j<1000)
{
potriviri[j]=i-wl+1;
++j;
}
x=match[x];
}
}*/
output<<x<<"\n";
for (i=0;i<j;++i)
output<<potriviri[i]<<" ";
return 0;
}