Pagini recente » Cod sursa (job #2289684) | Cod sursa (job #171352) | Cod sursa (job #1152325) | Cod sursa (job #614087) | Cod sursa (job #574469)
Cod sursa(job #574469)
#include<fstream>
#define nmax 2000010
using namespace std;
//no comment
char a[nmax],b[nmax];
int p[nmax],n,m,sol[1010],s=0;
void citire()
{
ifstream in("strmatch.in");
in.getline(a+1,2000005,'\n');
in.getline(b+1,2000005,'\n');
m=strlen(a+1);
n=strlen(b+1);
a[0]=' ';
b[0]=' ';
}
void prefix()
{
int i,j,k=0;
for (i=2;i<=m;i++)
{
while (k&&a[i]!=a[k+1])
k=p[k];
if (a[k+1]==a[i])
k++;
p[i]=k;
}
}
ofstream out("strmatch.out");
void verif()
{
int i;
out<<b+1<<'\n';
out<<a+1<<'\n';
for (i=1;i<=m;i++)
out<<p[i]<<"";
}
int main()
{
int i,j,k=0;
citire();
prefix();
//verif();
for (i=1;i<=n;i++)
{
while (k&&a[k+1]!=b[i])
k=p[k];
if (a[k+1]==b[i])
k++;
if (k==m)
{
k=p[m];
//mem solutie
s++;
if (s<=1002)
sol[s]=i-m+1;
}
}
out<<s<<'\n';
for (i=1;i<=s&&i<=1000;i++)
out<<sol[i]-1<<" ";
}