Тема: pomogite ,plz, naiti oshibku v kode

Vot zadachka

http://www.olymp.krsu.edu.kg/GeneralPro … ormat=html

Ya ee reshil s pomochu hasha.

U menya WA10.

Vot moi Kod :

#include <cstring>
#include <algorithm>
#include <iostream>
#include <fstream>
using namespace std;
#define ULL __int64
const ULL base = 97;

char s[2000000];
char s1[100001];
int n,l,m;

ULL hashes[2000000];

int main()      
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    gets(s);
    scanf("%d %d\n",&n,&l);

    ULL hsh= 0;
    ULL pw = 1;
    
    for (int i=0;i<l;i++)  {
        hsh=hsh*(ULL)base+(ULL)(s[i]-31);
        if (i!=l-1) pw=pw*(ULL)base;
    }

    hashes[m++] = hsh;
    
    int len = strlen(s);
    for (int i=1;i<len-l+1;i++) {
        hsh=hsh-(ULL)(s[i-1]-31)*pw;
        hsh=hsh*(ULL)base+(ULL)(s[i+l-1]-31);
        hashes[m++] = hsh;
    }

    sort(hashes,hashes+m);

    for (int j=0;j<n;j++) {         
        for (int i=0;i<l;i++) s1[i]=getchar();
        scanf("\n");
        ULL hsh=0;
        for (int i=0;i<l;i++) hsh=hsh*(ULL)base+(ULL)(s1[i]-31);

        if (binary_search(hashes,hashes+m,hsh))  puts("Yes"); else
        puts("No");
    }
}

2

Re: pomogite ,plz, naiti oshibku v kode

Посмотрел только чтение, вот этот момент подозрителен:

scanf("%d %d\n",&n,&l);

Ну и по аналогии:

scanf("\n");

Дело в том, что этот "\n" в формате для scanf ведёт себя немного хитро. Он пропускает не только перевод строки - а все whitespace'ы, т.е. если следующая строка начинается с пробела, то и они будут пропущены.

Соответственно, если вы хотите пропустить именно перевод строки, то надежней вызывать gets.

Re: pomogite ,plz, naiti oshibku v kode

Uraaaa!!!! Accepted !!! lol

Spasibo bolshoe!!!

4

Re: pomogite ,plz, naiti oshibku v kode

Гы smile Вот так бывает, даже не пришлось условие задачи читать и вникать в код smile


Кстати, на такое неожиданное поведение scanf я сам когда-то "напоролся" - посадил такую багу в авторском решении, хорошо её вовремя заметили smile

Re: pomogite ,plz, naiti oshibku v kode

e-maxx пишет:

Посмотрел только чтение, вот этот момент подозрителен:

scanf("%d %d\n",&n,&l);

Что здесь подозрительное? Скажи, пожалуста, я не вижу.

6

Re: pomogite ,plz, naiti oshibku v kode

Zayakin_Andrey
Эмм, я вроде бы дальше описал, в чём проблема smile

Re: pomogite ,plz, naiti oshibku v kode

спасибо=)

8

Re: pomogite ,plz, naiti oshibku v kode

код кидаю прямо сюда
да и вообще суффиксный массив можно написать ещё быстрее чуть ли не с асимптотикой как у дерева..просто почитать надо. я писал самый простой вариант .

Our excellent online comptia a+ training programs will lead you to success in the security+ training We also offer latest network test and www.principiacollege.edu