Cod sursa(job #1517113)

Utilizator antanaAntonia Boca antana Data 3 noiembrie 2015 21:06:28
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include<cstdio>
#include<string.h>
#define n1 100007
#define n2 100021
using namespace std;
char s1[2000001], s2[2000001];
int poz[1100];
int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out","w", stdout);
    int nr1=0, nr2=0, k1, k2, a1=0, a2=0, i, k=0, put1=1, put2=1;
    gets(s2);
    k2=strlen(s2);
    gets(s1);
    k1=strlen(s1);
    if(k2>k1)
        printf("0\n");
    else{
    for(i=0;i<k2;i++)
    {
      nr1=((nr1*123)%n1+s2[i])%n1;
      nr2=((nr2*123)%n2+s2[i])%n2;
      if(i!=0){
        put1=(put1*123)%n1;
        put2=(put2*123)%n2;
      }
    }
    for(i=0;i<k2;i++)
    {
      a1=((a1*123)%n1+s1[i])%n1;
      a2=((a2*123)%n2+s1[i])%n2;
    }
    if(a1==nr1&&a2==nr2)
      poz[++k]=0;
    for(i=1;i<=k1-k2;i++)
    {
      //a1=(nr1-(put1*s1[i-k2])%n1+n1)%n1;
      a1=a1-(put1*s1[i-1])%n1;
      if(a1<0)
        a1+=n1;
      //a1%=n1;
      //a2=(a2-(put2*s1[i-k2])%n2+n2)%n2;
      a2=a2-(put2*s1[i-1])%n2;
      if(a2<0)
        a2+=n2;
      a1=((a1*123)%n1+s1[i+k2-1])%n1;
      a2=((a2*123)%n2+s1[i+k2-1])%n2;
      if(a1==nr1&&a2==nr2){
        k++;
        if(k<=1000)
            poz[k]=i;
      }
    }
    a1=min(k, 1000);
    printf("%d\n", k);
    for(i=1;i<=a1;i++)
    {
      printf("%d ", poz[i]);
    }
    }
    return 0;
}