Cod sursa(job #1010997)

Utilizator h_istvanHevele Istvan h_istvan Data 16 octombrie 2013 00:35:09
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 kb
#include <stdio.h>
#include <string.h>
#include <vector>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define MAXN 2000001
#define MOD 100007
#define MOD2 100021
#define BASE 256

using namespace std;

char A[MAXN],B[MAXN];
int n,m;
vector<int> matches;

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    
    scanf("%s %s", A, B);

    n = strlen(A);
    m = strlen(B);
          
    if (m >= n)
    {
        int hash = 0, kutya = 0;
        FOR (i,0,n-1)
        {
            hash = (hash*BASE + A[i]) % MOD;
            kutya = (kutya*BASE + A[i]) % MOD2;
        }
        
        int hash2 = 0,kutya2 = 0;
        FOR (i,0,n-1)
        {
            hash2 = (hash2*BASE + B[i]) % MOD;
            kutya2 = (kutya2*BASE + B[i]) % MOD2;
        }
            
        int exp = 1, exp2 = 1;
        FOR (i,1,n-1)
        {
            exp = (exp*BASE) % MOD;
            exp2 = (exp2*BASE) % MOD2;
        }
            
        if (hash == hash2 && kutya == kutya2)
           matches.push_back(0);
            
        FOR (i,n,m-1)
        {
            hash2 = (hash2 - exp*B[i-n]) % MOD;
            hash2 = (hash2*BASE + B[i]) % MOD;
            kutya2 = (kutya2 - exp2*B[i-n]) % MOD2;
            kutya2 = (kutya2*BASE + B[i]) % MOD2;
            while (hash2 < 0) hash2+=MOD;
            while (kutya2 < 0) kutya2+=MOD2;
            
            if (hash == hash2 && kutya == kutya2 && matches.size() < 1000)
               matches.push_back(i-n+1);
        }
    }
    
    printf("%d\n",matches.size());
    vector<int>::iterator it;
    for (it = matches.begin(); it != matches.end(); ++it)
    {
        printf("%d ",*it);
    }
    
    return 0;
}