FR_10_19 - Wiadomość

[manjaro]

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…

[narbej]

Nie wydaję mi się że ten algorytm jest tak zły aby przekraczał 1s…

A jednak …

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

[manjaro]

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]

@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]

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

[hipcia]

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

[manjaro]

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;
                   }
               } 
           }