1k_trash's blog

By 1k_trash, 10 years ago, translation, In English

I'd like to solve some related problems.

HORRIBLE (from Spoj) has been solved.

Thank you.

Full text and comments »

  • Vote: I like it
  • +1
  • Vote: I do not like it

By 1k_trash, 10 years ago, In English

Hi everyone!

A while ago I've decided to learn Aho-Corasick algorithm and found the following problem at spoj.com:

  • Input to the program consists of a series of lines. The first line contains the string M (no more than 100000 characters long). The next line contains an integer N (<1000) the number of query strings. Each of the next N lines contain a string S (each of which is no more than 2000 characters long). Output should consist of N lines each with a character 'Y'/'N' indicating whether the string S is a substring of String M or not.

I've implemented Aho-Corasick algo and received CRASH. I think, it's a normal situation for such input size.

Now I'd like to know, is this problem solvable using Aho-Corasick or only suffix tree fits in given constraints?

Thanks.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By 1k_trash, 10 years ago, translation, In English

Sup, guys!

Let's consider the following problem: we have a set of strings (initially empty) and must handle two types of queries:

  1. Add new string to the set.
  2. For some input string do a check, if some string from the set occurs in the input string as a substring.

That's all. Of course, time/memory consuming should be as low as possible. Now I don't have an idea better than "Okay, let's use Aho-Corasick algo and each time, when we face query 1, let's destroy our old automaton and create a new one from scratch".

Thanks for your help.

Full text and comments »

  • Vote: I like it
  • +26
  • Vote: I do not like it

By 1k_trash, 10 years ago, translation, In English

You are given a string (|S| <= 10^5) and have to find such substring that repeats one after another maximum number of times. Or, if there are some such substrings, you must choose the longest/shortest/lexicografically_something.

For example: for test bacacacb answer is ac.

How to solve it? Thanks!

Full text and comments »

  • Vote: I like it
  • +6
  • Vote: I do not like it

By 1k_trash, 10 years ago, translation, In English

Hi, guys!

Today I tried to learn Graham Scan algorithm, but failed :(

Can you help me to find a bug in this code, please? http://ideone.com/IXFfS9 Algorithm is simple, but I still can't understand, why I have WA4 in problem A here http://codeforces.com/gym/100173

Can't even to find a test that can crash my solution :(

Thanks a lot!

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By 1k_trash, 11 years ago, In English

May somebody recommend some? Thanks.

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it