Aug 2019
1 / 7
Aug 2019
Aug 2019
manjaro
Aug '19

Witam serdecznie po dłuższej nieobecności.
W zadaniu w/w ciągle przekraczam limit czasu.
Proszę tylko o ocenę czy algorytm który wymyśliłem jest rzeczywiście zbyt wolny…

  1. Biore pierwszy znak szukanego podciągu i sprawdzam czy występuje w szukanym słowie.
  2. Jeśli występuję to biorę kolejną literę podciągu i szukam jej w daleszej częsci słowa
  3. Jeżli wszystkie litery podciągu występują daje YES
  4. Powtarzam procedurę dla każdego podciągu.

Program wyrzuca “przekroczono limit czasu” zawsze po 9 tescie…
Nie wydaję mi się że ten algorytm jest tak zły aby przekraczał 1s…

  • created

    Aug '19

  • last reply

    Aug '19
  • 6

    replies

  • 613

    views

  • 3

    users

  • 1

    link

narbej
Aug '19
1

A jednak …

No i wyrabia sie, jak sam zaznaczyles, tylko na 8 testach …

manjaro
Aug '19
1

No niby tak ale fizycznie szybciej się chyba nie da. Mój algorytm przeszukuje tylko 1 raz cały ciąg.
W sumie cały algorytm bazuje na 1 pętli

for (auto it=podciag.begin();it!=podciag.end();it++) {
               pozycja = ciag.find(*it);

               if (pozycja!=std::string::npos) {
                   ciag=ciag.substr(pozycja+1);

               } else {
                   break;
               }
           }
hipcia
Aug '19

@manjaro ja równieź zrobiłem to w jednej pętli i zaliczyłem kod z czasem 0.20 (z wyłączoną synchronizacją IO C z C++ itp.). Wstaw do kodu:

std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);

Jeżeli dalej przekraczasz czas to coś jest nie tak w kodzie. Wydaje mi się, że niepotrzebnie używasz std::string::substr. Mój sposób (w funkcji):

  1. Biorę pierwszy znak szukanego ciągu.
  2. Jeżeli nie znalazł się w wyrażeniu zwracam false.
  3. Jeżeli znalazł się ustawiam iterator dla wyrażenia o 1 za znalezioną pozycją
  4. Dla kolejnych znaków szukam od zapisanej pozycji…
  5. Jeżeli pętla się skończy zwracam true.
manjaro
Aug '19
1

Przeszło ze słabym czasem 1:14
Wydaje mi się że problemem było użycie std::sring::find
Tutaj9 więcej na ten temat

hipcia
Aug '19

std::string::find jest ok (drugi parametr bardzo przydatny).

manjaro
Aug '19

Zrobiłem bez tego find na jednej pętli podobnie do Twojego schematu ale wyrzuciłem tego wartownika bo nie jest potrzebny a kod i tak wykonuje się ponad sekunde… Oczywiście synchronizacja wyłączona.

           std::string::iterator itr=podciag.begin();
  
           for (std::string::iterator it=ciag.begin();it!=ciag.end();it++) {
               if (*it==*itr) {
                   itr++;
                   if (itr==podciag.end()) {
                       break;
                   }
               } 
           }