Блог пользователя sw1ft

Автор sw1ft, история, 8 лет назад, По-английски

Hey everyone. Yesterday I found problem UVa 10679 — I Love Strings!!, solved it using C++ Strings and KMP, and got a runtime of 1.080/3.000s. I found this rather high so I looked for the problem on the web and found on Algorithmist that this problem perfectly suits Aho-Corasick, so I found this guide and solved the problem based on that, but I'm getting TLE. After this I was a little bit confused, but maybe such implementation is just slow. Then I checked the Problem Stats and found that morris821028's solution is ranked 17 with a runtime of 0.016, so I thought he must have implemented Aho-Corasick in a (much) faster way. Right after this I looked for his solution: turns out he used KMP, just like me, but with C-Style strings instead...

Are C-Style Strings really this faster or is this just an especial case?

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I just submitted the solution from the github page and it took 1.090s, so I think the solution on github is not the one he got the 0.016s time with.

The fact that his github solution took 1.090s shows that for this problem the speed difference between std::string and C-Style strings is negligible.