Palindromic Query - Codeforces

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

Palindromic Query

Автор YouKn0wWho, история, 8 лет назад, По-английски

I am stuck on this following problem:

Statement:

Given a string of size n and q queries of type (l,r) you need to find how many palindromes are there in the substring of range [l...r].

Constraints:

1<=n,q<=100000

1<=l<=r<=n

Thanks for reading the problem. It will be really helpful if you can give me a solution.

palindrome

YouKn0wWho
8 лет назад
25

Комментарии (24)

Показать архивные | Написать комментарий?

allllekssssa

8 лет назад, скрыть # |

← Rev. 2 →

Mistake in approach.

→ Ответить

YouKn0wWho

8 лет назад, скрыть # ^ |

Thanks for your reply.

But I am not clear about the merging procedure. Can you please tell me more about this part "number of palindromes between this parts (left end in first half and right in second)."

→ Ответить

fugazi

8 лет назад, скрыть # ^ |

← Rev. 2 →

why even O((r - l) * logn)? You can preprocess string using Manachar's algorithm, and then for each i in [l, r], you can find the number of palindromes in between the parts, centered at i in O(1), so it's just O(r - l).

but I don't understand, how it will be O(nlog²n) in total, because you will have to merge even for queries. Can you please elaborate.

→ Ответить

YouKn0wWho

8 лет назад, скрыть # ^ |

← Rev. 2 →

[deleted]

→ Ответить

fugazi

8 лет назад, скрыть # ^ |

We know that there can be at most n palindromes in a string of size n

No there can be n² palindromes, for example consider aaaaaa.

so that won't work :|

→ Ответить

YouKn0wWho

8 лет назад, скрыть # ^ |

Sorry, you are right.

→ Ответить

allllekssssa

8 лет назад, скрыть # ^ |

← Rev. 3 →

Mistake in approach.

→ Ответить

fugazi

8 лет назад, скрыть # ^ |

"each interval will be smaller in at most logn merges"

No, you may even have to merge already merged intervals, with a simple interval. So that won't be O(nlogn)

→ Ответить

allllekssssa

8 лет назад, скрыть # ^ |

You are absolutely right! I will try to invent something better and correct :)

→ Ответить

fugazi

8 лет назад, скрыть # |

← Rev. 2 →

Sqrt-decomposition solution is costly but may pass, depending on TL.

Whenever you add/remove some index, you have to add/remove palindromic substrings ending at that index, which you can find using binary search (hash the string and it's reverse).

Total complexity will be $\text{[math]}$

→ Ответить

allllekssssa

8 лет назад, скрыть # ^ |

How will you find palindromic substrings ending at some index by binary search?

→ Ответить

fugazi

8 лет назад, скрыть # ^ |

Hashing

Hash the given string and it's reverse, Now you can binary search on the maximum length that can be a palindrome ending at that index (in the direction you want). To check if the substring of given length is palindrome, you just compare hash of string with it's reverse, for that substring.

→ Ответить

allllekssssa

8 лет назад, скрыть # ^ |

← Rev. 2 →

That is not correct, you can do it for center of string, otherwise function is not monotonic and you can not use binary search:

Just look at string aba, there is two palindromes and binary search will check first ba and say, ok it is not palindrome answer is smaller than 2.

→ Ответить

fugazi

8 лет назад, скрыть # ^ |

oh ok.. missed it :(

→ Ответить

allllekssssa

8 лет назад, скрыть # ^ |

1:1 in hacks, we are playing until 2 ;)

→ Ответить

Noam527

8 лет назад, скрыть # |

+20

It is easier to explain by considering only palindromes centered at indicies (so, odd length), the idea is the same anyway. For each index i, r_i will be the longest radius of a palindrome centered there (in other words, the amount of palindromes centered at index i). Directly from manacher, this takes $\text{[math]}$ to calculate.

For a query [l, r], we first compute $\text{[math]}$ . Now we want to calculate

$\text{[math]}$

Again, thanks to symmetry, I'll only explain how to compute the left term.

$\text{[math]}$ .

The sum over i can be found in constant time. As for the other term, if we create some array r_i' = r_i - i during the preprocessing, then the queries are asking for some over range of min(C, r_i') where C is constant. You can solve this in $\text{[math]}$ per query using wavelet tree, and I guess it's also solvable with a persistent segtree.

→ Ответить

YouKn0wWho

8 лет назад, скрыть # ^ |

← Rev. 2 →

Thanks for your reply. This is an interesting approach.

Well, I am interested to know about this idea- min(i-l+1,r[i])=i+min(1-l,r[i]-i).

I have brute forced for different i,l and r[i] and found that this is true. But curious mind wants to know the proof of this. If you can come up with a proof feel free to share this with me.

Thanks again.

→ Ответить

fugazi

8 лет назад, скрыть # ^ |

min(i - l + 1, r_i) = min(i + (1 - l), i + (r_i - i)) = i + min(1 - l, r_i - i)

→ Ответить

Noam527

8 лет назад, скрыть # ^ |

min(x + a, y + a) = a + min(x, y). I think this is fairly obvious, but you can do case analysis anyway:

x < y: min(x + a, y + a) = x + a = a + min(x, y).
x ≥ y: min(x + a, y + a) = y + a = a + min(x, y).

Now just plug a = i, x = 1 - l, y = r_i - i

→ Ответить

YouKn0wWho

8 лет назад, скрыть # ^ |

thanks. got it

→ Ответить

I_love_myself

8 лет назад, скрыть # |

← Rev. 2 →

Palindrome tree can tall you, how many palindrome add s[i]. You can create partial sum array and say on query O(1).
Sorry for my English.

→ Ответить

pirates23

6 лет назад, скрыть # |

+14

Please provide problem link.I want to solve it.

→ Ответить

MidoriFuse

6 лет назад, скрыть # ^ |

Happy solving

→ Ответить

SPyofgame

6 лет назад, скрыть # |

My approach takes O(n ^ 2) precalculation to get O(1) queries.

Can I improve furthur more with dynamic programming ?

My code

void solve() {
    string s;
    cin >> s;
  
    vector<vector<int> > precal(2, vector<int>(n, +INF));
    /// precal0[x] - min position (p) | (0 + p)..(x)_(x + 1)..(x + p) is palindrome
    /// precal1[x] - min position (p) | (0 + p)......(x)......(x + p) is palindrome

    const int lower = -1, upper = n;
    for (int i = 0; i < n; ++i) /// Precalculation O(n ^ 2)
    {
        for (int l = i, r = i + 0; lower < l && r < upper; --l, ++r)
            if (s[l] == s[r]) precal[1][i] = l; else break;

        for (int l = i, r = i + 1; lower < l && r < upper; --l, ++r)
            if (s[l] == s[r]) precal[0][i] = l; else break;
    }

    for (int q = readInt(); q--; ) /// O(q) | O(1) per query
    {
        int l = readInt() - 1;
        int r = readInt() - 1;

        bool type = (r - l + 1) & 1; /// Odd or Even Size palindrome
        int m = (l + r) / 2;         /// Middle of palindrome
        cout << (precal[type][m] <= l ? 1 : -1) << '\n';
    }
}

→ Ответить