Cod sursa(job #1010993)

Utilizator h_istvanHevele Istvan h_istvan Data 16 octombrie 2013 00:21:34
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 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 65537
#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;
        FOR (i,0,n-1)
            hash = (hash*BASE + A[i]) % MOD;
        
        int hash2 = 0;
        FOR (i,0,n-1)
            hash2 = (hash2*BASE + B[i]) % MOD;
            
        int exp = 1;
        FOR (i,1,n-1)
            exp = (exp*BASE) % MOD;
            
        if (hash == hash2)
           matches.push_back(0);
            
        FOR (i,n,m-1)
        {
            hash2 = (hash2 - exp*B[i-n]) % MOD;
            hash2 = (hash2*BASE + B[i]) % MOD;
            
            if (hash == hash2 && 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;
}