Cod sursa(job #1010979)

Utilizator h_istvanHevele Istvan h_istvan Data 15 octombrie 2013 23:50:42
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <stdio.h>
#include <vector>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define MAXN 2000001
#define MOD 65535
#define BASE 256

using namespace std;

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

inline bool validChar(char c)
{
     return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9');
}

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

    n = m = 1;
    while (validChar(A[n]))
          n++;
    while (validChar(B[m]))
          m++;
          
    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.push_back(i-n+1);
    }
    
    printf("%d\n",matches.size());
    FOR (i,0,matches.size()-1)
    {
        printf("%d ",matches[i]);
        if (i == 999)
           break;
    }
    
    return 0;
}