What is the most efficient algorithm when the problem gives you a string of N length and asks you to answer in Q queries if the ith word of length M (where M is much lesser than N -> M << N) is contained into 'N length word' ?

Thanks in advance !

Before contest

Manthan, Codefest 19 (open for everyone, rated, Div. 1 + Div. 2)

06:14:20

Register now »

Manthan, Codefest 19 (open for everyone, rated, Div. 1 + Div. 2)

06:14:20

Register now »

*has extra registration

# | User | Rating |
---|---|---|

1 | tourist | 3645 |

2 | Radewoosh | 3403 |

3 | Um_nik | 3348 |

4 | LHiC | 3336 |

5 | Benq | 3316 |

6 | V--o_o--V | 3275 |

7 | mnbvmar | 3241 |

8 | yutaka1999 | 3190 |

9 | ainta | 3180 |

10 | Petr | 3106 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 191 |

2 | Radewoosh | 176 |

3 | PikMike | 165 |

4 | rng_58 | 164 |

5 | Vovuh | 160 |

6 | majk | 158 |

7 | antontrygubO_o | 154 |

7 | 300iq | 154 |

9 | Um_nik | 151 |

10 | kostka | 149 |

What is the most efficient algorithm when the problem gives you a string of N length and asks you to answer in Q queries if the ith word of length M (where M is much lesser than N -> M << N) is contained into 'N length word' ?

Thanks in advance !

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/25/2019 11:20:41 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Well, if M is really small, you can compute hash for all possible words of size <= M inside the string N. Then, just compute the hash for the ith word and check if the same hash was found inside the string N.

Edit: this would be O(n*m + q*m)

Could anyone tell me if that will work?

You can compute the suffix array for the string of length N and then answer each query in

O(M*_{log}N), making the algorithmO(Q*M*_{log}N). If M is small, it should run in time.I just know a MlogN algorithm. How I will get that in O(M) ?

Yes, you're right. I fixed the typo. I'd need to know the actual constraints, but I guess this solution should be fast enough.

I think you can get O(M) per query using suffix automaton.

Yep. Just build a suffix automaton on the string of length N and after that for each query run a dfs from the start node of the automaton. If you can do all M transitions between the automaton states then the small string is contained in the big one. The time complexity is

O(M)*O(Q)=O(M*Q).I think the most efficient algorithm for this kind of problems is Aho–Corasick