nam2012abcd's blog

Looking for online judge string matching problem
By nam2012abcd, history, 9 years ago, In English

Hi everyone!

I'm looking for classic problem: Given a string A and Q strings B_1, B_2, .., B_Q. For each i count the number of occurrence of the string B_i in string A.

Can you give me the link to the above problem in some online judge sites. Thanks

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

1449 — Dominating Patterns

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

String Matching
String Multimatching

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Take a look at this page: http://www.ahmed-aly.com/Category.jsp?ID=35. The first and fourth problems are a bit simpler than what you described (you just have to answer whether Bi appears in A). The second is similar to them but takes place in a grid. The third is also slightly easier than what you described. I guess you're probably interested in them, though, because the idea is the same — just a small modification.

Anyway, Frequency Count is pretty much equivalent to what you're asking. Finally, I'd like to recommend USACO — Censoring (Gold Division), which is about the same difficulty. It's nice because it forces you to notice something important to avoid receiving TLE in a given testcase.

→ Reply