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

[HELP] combinatorics on strings
Автор baddestguy, история, 4 года назад, По-английски

I want to find the number of strings that are lexicographically smaller than A and has substring B NOTE: the length of the strings should be <= |A|.

e.g. A = "da" and B = "c" then answer = 29: {'c', 'ac', 'bc', cX}, where X is any alphabet. also, constraints are pretty low, 1 <= |B|,|A| <= 1000 Please help thanks.

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

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

Does "contains" mean "subsequence" or "substring"? Is "smaller" lexicographically smaller or anything else?

→ Ответить
  • »
    »
    4 года назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    it means substring, and smaller means lexicographically smaller

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Is the number of such strings not infinite in your case? "c", "ca", "caa", "caaa", "caaaa" etc all have "c" as a substring and are lexicographically smaller than "da".

      → Ответить
      • »
        »
        »
        »
        4 года назад, # ^ |
        ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        Oh, then the length of the strings should be <= |A|.

        is there a name for this type of ordering cause I think I'm not phrasing it correctly?

        → Ответить
        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится

          I don't think it has a standard name, you just had to be more explicit.

          Anyway, I think your problem can be solved with dynamic programming, states like this: $$$\mathrm{dp}[i][j][a][b]$$$ counts the number of strings lexicographically smaller than $$$A$$$, where:

          • $$$i$$$ is the length of the string;
          • $$$j$$$ is the length of the longest suffix of the string that is also a prefix of $$$B$$$;
          • $$$a$$$ is 0 if the string is a prefix of $$$A$$$, 1 otherwise;
          • $$$b$$$ is 0 if the string does not contain $$$B$$$ as a substring, 1 otherwise.

          I think you should be able to do updates in a KMP-like way.

          → Ответить