Cod sursa(job #1516597)

Utilizator ericutzdevilEric Spataru ericutzdevil Data 3 noiembrie 2015 11:03:52
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include<cstdio>
#include<cstring>

using namespace std;

int put (int a,int b){
    int p=1,i;
    for (i=1;i<=b;i++)
        p*=a;
    return p;}

int main()

{

freopen ("strmatch.in","r",stdin);
freopen ("strmatch.out","w",stdout);

int n1=100007,n2=100021,i;
long long nr1,nr2;
char s1[200000],s2[200000],endLine;

gets(s2);
scanf ("%c",&endLine);
gets(s1);

int k2=strlen(s2),k1=strlen(s1);

nr1=0;nr2=0;

for (i=0;i<=k2-1;i++){
    nr1=((nr1*123)%n1+s2[i])%n1;
    nr2=((nr2*123)%n2+s2[i])%n2;}

int kappa1=0,kappa2=k2,nrr1,nrr2,z=0,pozic[1001];

for (i=0;i<=k2-1;i++)
    {nrr1=((nrr1*123)%n1+s1[i])%n1;
    nrr2=((nrr2*123)%n2+s1[i])%n2;}

if (nrr1==nr1&&nrr2==nr2){
    pozic[++z]=0;}

while (i<k2){
    nrr1=0;nrr2=0;
    for (i=kappa1;i<kappa2;i++){
        nrr1=nrr1-(s1[i]*(put(123,k2-1)%n1)%n1);
        while (nrr1<0){
            nrr1+=n1;}
        nrr1=(nrr1+(s1[i]))%n1;
        while (nrr1<0){
            nrr1+=n1;}
        nrr2=nrr2-(s1[i]*(put(123,k2-1)%n2)%n2);
        while (nrr2<0){
            nrr2+=n2;}
        nrr2=(nrr2+(s1[i]))%n2;
        while (nrr2<0){
            nrr2+=n2;}
        if (nrr1==nr1&&nrr2==nr2){
            pozic[++z]=i;}}
    kappa1++;kappa2++;}

printf ("%d\n",z);
for (i=1;i<=z;i++)
    printf ("%d ",pozic[i]);

return 0;
}