Pagini recente » Cod sursa (job #3171195) | Cod sursa (job #2095843) | Cod sursa (job #73522) | Cod sursa (job #1779059) | Cod sursa (job #1970897)
#include <fstream>
#include <cstring>
#define nmax 2000002
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);
fin.getline(s,nmax);
}
void temp_suffix_build()
{
int i=1,j=0;
while(k[i]!=NULL)
{
if(k[i]==k[j])
{
t[i]=j+1;
i++;j++;
}
else
{
while((k[j]!=k[i])&&j)
{
j=t[j-1];
}
if(k[j]!=k[i])
{
t[i]=j;
}
else
{
t[i]=j+1;
}
i++;
}
}
}
int c=0;
void searcha()
{
int i=0,j=0;
int m=strlen(k);
while(s[i]!=NULL)
{
if(s[i]==k[j])
{
i++;
j++;
}
else
{
while(j&&s[i]!=k[j])
{
j=t[j-1];
}
}
if(j==0&&s[i]!=k[j])
{
i++;
}
if(j==m)
{
c++;
if(c>1000)
{
break;
}
else
{
v[c]=i-m;
}
}
}
}
void afis()
{
std::fstream fout("strmatch.out",std::ios::out);
fout<<c<<"\n";
for(int i=1;i<=c;i++)
{
fout<<v[i]<<" ";
}
}
int main()
{
citire();
temp_suffix_build();
searcha();
afis();
return 0;
}