Pagini recente » Cod sursa (job #1561116) | Cod sursa (job #2939571) | Cod sursa (job #627248) | Cod sursa (job #2731673) | Cod sursa (job #1970984)
#include <fstream>
#include <cstring>
#define nmax 2000005
using namespace std;
char s[nmax];
char k[nmax];
int t[nmax];
int v[1002];
void citire()
{
std::fstream fin("strmatch.in",std::ios::in);
fin.getline(k,nmax-1);
fin.getline(s,nmax-1);
int n=strlen(s);
int m=strlen(k);
for(int i=n;i>=1;i--)
{
s[i]=s[i-1];
}
for(int i=m;i>=1;i--)
{
k[i]=k[i-1];
}
s[0]=' ';
k[0]=' ';
s[n+1]=NULL;
k[m+1]=NULL;
}
void temp_suffix_build()
{
int j=0;
for(int i=2;k[i]!=NULL;i++)
{
while(k[j+1]!=k[i]&&j)
{
j=t[j];
}
if(k[j+1]==k[i])
{
j++;
}
t[i]=j;
}
}
int c=0;
void searcha()
{
int i=0,j=0;
int m=strlen(k);
for(int i=1;s[i]!=NULL;i++)
{
while(j&&s[i]!=k[j+1])
{
j=t[j];
}
if(s[i]==k[j+1])
{
j++;
}
if(j==m-1)
{
j=t[j];
c++;
if(c<=1000)
{
v[c]=i-m+1;
}
}
}
}
void afis()
{
std::fstream fout("strmatch.out",std::ios::out);
fout<<c<<"\n";
for(int i=1;i<=min(c,1000);i++)
{
fout<<v[i]<<" ";
}
}
int main()
{
citire();
temp_suffix_build();
searcha();
afis();
return 0;
}