### The_Orion's blog

By The_Orion, history, 5 weeks ago, Sorry for disturbing you .

I was trying to solve this SPOJ problem , but failed .

Any suggestion ? Hint ? Tutorial ? Or solution ?  Comments (6)
 » The maximum possible answer is around $10^5$ (or less), just bruteforce over all numbers and check if they occurs should work.
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   You can't check the occurrences naively. The complexity will be $O(10^5 \cdot n)$. You can either precalculate all numbers under $10^5$ that occurs or build a suffix-automaton on the string.
•  » » » » I don't know about suffix-automaton. Can you help with a sample code or tutorial link ?
•  » » » » » No need to use that. The easiest way to get AC is: code#include char s; int n; int main() { scanf("%s",s+1); n = std::strlen(s+1); std::setS; for (int l = 1; l <= n; ++ l) { int x = 0; for (int r = l; r <= l + 7 && r <= n; ++ r) { x = x * 10 + s[r] - '0'; S.insert(x); } } int p = 1; while (S.find(p) != S.end()) p ++; printf("%d",p); return 0; }