Cod sursa(job #1468969)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 7 august 2015 13:32:21
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <cstdio>
#include <vector>
#define LMAX 2000007
#define MOD 100007
using namespace std;
char a[LMAX],b[LMAX];
int p[LMAX],h1[1005],cat;
int main()
{
    freopen ("strmatch.in","r",stdin);
    freopen ("strmatch.out","w",stdout);
    char ch;
    int p1=0;
    while(1)
    {
        scanf("%c",&ch);
        if(ch=='\n') break;
        a[++p1]=ch;
    }
    p[0]=1;
    for(int i=1;i<p1;i++)
    {
        p[i]=p[i-1]*26;
        p[i]%=MOD;
    }
    int val=0,key=0;
    for(int i=1;i<=p1;i++)
    {
        scanf("%c",&b[i]);
        val+=p[p1-i]*(a[i]-'A');
        val%=MOD;
        key+=p[p1-i]*(b[i]-'A');
        key%=MOD;
    }
    if(val==key) h1[++cat]=0;
    for(int i=p1+1;;i++)
    {
        scanf("%c",&ch);
        if(feof(stdin)) break;
        b[i]=ch;
        key=key-(p[p1-1]*(b[i-p1]-'A')%MOD);
        key*=26;
        key%=MOD;
        key+=p[0]*(b[i]-'A');
        if(val==key&&cat<1000) h1[++cat]=i-p1;
    }
    printf("%d\n",cat);
    for(int i=1;i<=cat;i++) printf("%d ",h1[i]);
}