Analiza programów

17.06.2009

Koledzy z klasy

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define MOD 33554435 //REV: czemu nie const int?
using namespace std;
typedef long long LL;//REV: dlaczego ze znakiem?
typedef vector<int> VI;
typedef pair<int,int>PII;
typedef vector<VI>VII;
char A[500003], B[500003];//REV: bez tego "3" chyba nie działa, bo jest potrzebne aby hA[-1] było zainicjowane zerem :)
int hA[500003], hB[500003];
LL pot67[500003];//REV: dlaczego nie 32bitowy typ danych?
int da, db;
int f(char A)
{
    if(A-'A'<=26&&A-'A'>=0)return A-'A';
    if(A-'a'<=26&&A-'a'>=0)return A-'a'+26;
    if(A-'0'<=9&& A-'0'>=0)return A-'0'+52;//REV: jest jakiś else? bo jeśli tak, to stos się psuje, a jesli nie, to po co if ?
}
void pre()
{
    pot67[0]=1;
    for(int i=1;i<=500000;i++)pot67[i]=(pot67[i-1]*67)%MOD;//REV: na moje oko (MOD-1)*67 mieści się w uint32_t
    int i=0;
    LL w=0;
    for(i=0;i<da;i++)//REV: nie wiem czemu spodziewałem się tu Hornera
    {
        //if(k>MOD)k%=MOD;
        w=(w+f(A[i])*pot67[i])%MOD;//&33554431;//2^25-1
        hA[i]=w;//REV: teoretycznie overflow?
    }
    w=0;
    for(i=0;i<db;i++)
    {
        //if(k>MOD)k%=MOD;
        w=(w+f(B[i])*pot67[i])%MOD;//&33554431;//2^25-1
        hB[i]=w;
    }
    //for(int i=0;i<6;i++)printf("%d %d\n",hA[i],hB[i]);
    //printf("%d %d %d\n",(hB[4]-hB[0]), hA[3]*67%MOD, hA[4]);
}
int solve(int a,int b, int c)//REV: czemu nie unsigned?
{
    int w1=hA[a+c]-hA[a-1], w2=hB[b+c]-hB[b-1];//REV: teoretycznie a-1 może być [-1] (podobnie b-1)
    if(a<b)w1=(w1*pot67[b-a])%MOD;
    if(a>b)w2=(w2*pot67[a-b])%MOD;
    if(w1<0)w1+=MOD;//REV: woot? jak niby do tego dochodzi?
    if(w2<0)w2+=MOD;
    //printf("%d %d\n", w1,w2);
    if(w1==w2)return 1;//REV: niepotrzebny if
    return 0;      
}
int main()//REV: coś z wcięciami nieteges
{
   // printf("%d %d %d %d %d %d\n",f('A'),f('Z'),f('a'),f('z'),f('0'),f('9'));
    scanf("%s%s",A,B);
    da=strlen(A);db=strlen(B);
    int a,b,c;
    pre();
    scanf("%d%d%d",&a,&b,&c);
    while(a!=0&&b!=0&&c!=0)//REV: czy to aby na pewno poprawny warunek?
    {
        if(solve(a-1,b-1,c-1)==0)printf("NIE\n");
        else printf("TAK\n");
        scanf("%d%d%d",&a,&b,&c);
    }
    //system("pause");
return 0;
}
 

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com