Cod sursa(job #1867611)

Utilizator andysoloAndrei Solo andysolo Data 4 februarie 2017 11:15:17
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <cstring>
#define NMAX 2000005
#define M101 666013
#define M109 10003

using namespace std;

struct key
{
    int b101 ;
    int b109 ;
};
struct key sir, sub;
int k,l[NMAX];
char sir1[NMAX],sub1[NMAX];

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

    scanf("%s\n%s",sub1,sir1);
    int m=strlen(sub1);
    int n=strlen(sir1);

    int  P101 = 1;
    int  P109 = 1;

    for(int i=0; i<m; i++)
    {
        sub.b101 = (sub.b101*101+sub1[i])%M101;
        sub.b109 = (sub.b109*109+sub1[i])%M109;
        if(i!=0)
        {
            P101= (P101*101)%M101;
            P109= (P109*109)%M109;
        }
    }

    for(int i=0; i<m; i++)
    {
        sir.b101 = (sir.b101*101+sir1[i])%M101;
        sir.b109 = (sir.b109*109+sir1[i])%M109;
    }

    if(sir.b101 == sub.b101 && sir.b109 == sub.b109)
        l[++k]=0;

    for(int i=m; i<n; i++)
    {
        sir.b101 = ((sir.b101 - (sir1[i-m]*P101)%M101 + M101)*101 + sir1[i])%M101;
        sir.b109 = ((sir.b109 - (sir1[i-m]*P109)%M109 + M109)*109 + sir1[i])%M109;
        if(sir.b101==sub.b101 && sir.b109==sub.b109)
        {
            l[++k]=i-m+1;
        }
    }
    int s=0;
    printf("%d \n",k);
    if(k<=1000)
        s=k;
    else s=1000;
    for(int i=1; i<=s; i++)
        printf("%d ",l[i]);


    return 0;
}