infoarena

#include <cstdio>
#include <cstring>
#define NMAX 2000001
#define min(a,b) a<b ? a:b
using namespace std;

char A[NMAX],B[NMAX];
int n,m,nr,a,b;
int Sol[NMAX];
int t[NMAX];

inline unsigned long putere(int x,int k,int MOD){

    if (k == 0)
        return 1;
   else if(k%2 == 0){
       a = putere(x,k/2,MOD);
        return a*a%MOD;
   }
   else{
        a = putere(x,k/2,MOD);
        b = a*a%MOD;
        return b*x % MOD;
   }
}

inline int match(char *T, char *P,int j){

    for(register int i=0;i<m;++i)
        if(T[i+j] != P[i])
            return 0;
return 1;
}

inline void Rabin_Karp(char *T,char *M,int d,int MOD){

    unsigned long h,P=0;
    n = strlen(T);
    m = strlen(M);

        t[0] =0;
        h = putere(d,m-1,MOD);
    for(register int i=0;i<m;++i){
        P = (d*P + M[i])% MOD;
        t[0] = (d*t[0] + T[i])%MOD;
}

    printf("%d\n",P);
    for(register int i=0;i<=n-m;++i){

        printf("%d\n",t[i]);
        if(P == t[i]){
            if(match(T,M,i))
                    Sol[++nr] = i;
                    printf("%d\n",i);
                  }

         t[i+1] = (d*(t[i] - T[i+1]*h) + T[i+m+1])%MOD;
        }
}

int main(){


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

fgets(B,sizeof(B),stdin);
fgets(A,sizeof(A),stdin);

    Rabin_Karp(A,B,256,100003);
    printf("%d\n",nr);
    for(register int i=1;i<=min(nr,1000);++i)
        printf("%d ",Sol[i]);

return 0;
}

#include <fstream>
#include <string>
#include <vector>

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

string a,b;
vector<long> rez;
long i,poz=-1;

int main()
{
    getline(f,a);
    getline(f,b);

    poz=b.find(a,poz+1);
    while(poz!=string::npos)
    {
        rez.push_back(poz);
        poz=b.find(a,poz+1);
    }

    g<<rez.size()<<"\n";
    for(i=0;i<rez.size()&&i<1000;i++)
        g<<rez[i]<<" ";
    return 0;
}

void make_prefix(void)
{
    int i, q = 0;
 
    for (i = 2, pi[1] = 0; i <= M; ++i)
    {
        while (q && A[q+1] != A[i])
            q = pi[q];
        if (A[q+1] == A[i])
            ++q;
        pi[i] = q;
    }