Pagini recente » Cod sursa (job #932833) | Cod sursa (job #2437985) | Cod sursa (job #2808947) | Cod sursa (job #1323915) | Cod sursa (job #1887310)
#include <cstdio>
#include <cstring>
using namespace std;
char s1[2000010],s[2000010];
int prefix[2000010],n,m,q=0,x=0,pos[10000],ok=0,ok1=0;
void citire()
{
fgets(s1,2000010,stdin);
fgets(s,2000010,stdin);
s1[strlen(s1)-1]=0;
s[strlen(s)-1]=0;
m=strlen(s1);
n=strlen(s);
}
void prefix1()
{
prefix[0]=0;
int i=0,j=1;
while(j<=m-1)
{
if(s1[i]==s1[j])
{
prefix[j]=prefix[j-1]+1;
i++;
}
else
while(i>0&&s1[i]!=s1[j])
{
i=prefix[i-1];
ok=1;
}
if(ok==1&&i!=0)
prefix[j]=prefix[i+1]+1;
if(i==0)
prefix[j]=0;
j++;
ok=0;
}
}
void cerinta()
{
int j=0,l=0,i=0,nr=0;
while(i<=n-1)
{
while(s1[j]==s[i]&&i<=n-1)
{
i++;
j++;
l++;
}
if(l==m)
{
nr++;
}
if(s1[i]!=s[j])
{
while(j!=0&&s1[j]!=s[i])
{
j=prefix[j-1];
ok1=1;
}
}
l=j;
if(ok1==0)
i++;
ok1=0;
}
printf("%d\n",nr);
if(nr>1000)
nr=1000;
j=0;
l=0;
i=0;
while(i<=n-1&&nr!=0)
{
while(s1[j]==s[i]&&i<=n-1)
{
i++;
j++;
l++;
}
if(l==m)
{
nr--;
printf("%d ",i-l);
}
if(s1[i]!=s[j])
{
while(j!=0&&s1[j]!=s[i])
{
j=prefix[j-1];
ok1=1;
}
}
l=j;
if(ok1==0)
i++;
ok1=0;
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
citire();
prefix1();
cerinta();
//cout << "Hello world!" << endl;
return 0;
}