Comptage des sous-chaînes palindromiques en O (n)
Étant donné une chaîne (supposons uniquement des caractères anglais) S de longueur n, nous pouvons compter le nombre de sous-chaînes palindromiques avec l'algorithme suivant:
for i = 0 to |S| do
p1 = number of palindromes centered in i (odd length)
p2 = number of palindromes centered in i and i+1 (even length)
add p1 + p2 to total number of palindromic substrings of S
Le code ci-dessus est O(n^2) cependant.
Je suis intéressé par un algorithme qui résout ce problème dans O(n). Je sais avec certitude que l'un existe car j'ai entendu plusieurs personnes dire que c'est le cas, et le problème existe sur un site de juge en ligne local avec une limite supérieure de 1 000 000 sur n, mais je n'ai jamais vu le algorithme et ne peut pas sembler être en mesure de venir avec elle.
Mise à Jour:
L'idée générale que j'ai est de calculer len[i] = length of the longest palindrome centered at the character 2i + 1 et un tableau similaire pour les palindromes de longueur paire. Avec une bonne comptabilité, il devrait être possible de calculer cela en O(1) pour chaque caractère, ce qui nous permettra de compter beaucoup de palindromes à la fois. Je suis coincé sur la façon exactement de calculer cela cependant.
J'accepterai une solution qui utilise O(n) et peut-être même O(n log n) de la mémoire supplémentaire. Je pense c'est impossible sans elle.
Toutes les bonnes idées ou références sont appréciées.
3 réponses
Le site suivant montre un algorithme pour calculer la plus longue sous-chaîne palindromique en temps O (N), et le fait en calculant la plus longue sous-chaîne palindromique à chaque centre possible, puis en prenant le maximum. Donc, vous devriez être en mesure de le modifier facilement pour vos besoins.
Http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/
EDIT: le premier lien semble un peu fragile en regardant de plus près, alors en voici un autre un:
Http://zhuhcheng.spaces.live.com/Blog/cns!DE38E96268C49F28!311.entry?wa=wsignin1.0&sa=707413829
Pour les chaînes "normales", il devrait être plutôt efficace de considérer chaque caractère comme le "centre" potentiel d'un palindrome, puis de vérifier si les caractères environnants en construisent un:
# check odd palindromes
for center in range(len(ls)):
# check how many characters to the left and right of |center|
# build a palindrome
maxoffs = min(center, len(ls)-center-1)
offs = 0
while offs <= maxoffs and ls[center-offs] == ls[center+offs]:
offs += 1
offs -= 1
print ls[center-offs : center+offs+1]
# check for even palindromes
for center in range(len(ls)-1):
maxoffs = min(center, len(ls)-center-2)
offs = 0
while offs <= maxoffs and ls[center-offs] == ls[center+offs+1]:
offs += 1
offs -= 1
if offs >= 0:
print ls[center-offs : center+offs+2]
Pour les chaînes normales, cela devrait être à propos de O(n), bien que dans le pire des cas, par exemple si la chaîne se compose d'un seul caractère répété encore et encore, elle prendra toujours O (n2) temps.
Considérons une chaîne S="aaabb".
Ajoutez un caractère '$' aux deux extrémités de la chaîne et entre deux caractères consécutifs pour changer la chaîne en S="$a$a$a$b$b$" et appliquer l'algorithme de Manacher pour cette chaîne S.
La nouvelle chaîne {[4] } est de longueur 2n + 1 ce qui nous donne un temps D'exécution de O (2n + 1) qui est identique à O(n).
index : 1 2 3 4 5 6 7 8 9 10 11
A : 1 3 5 7 5 3 1 3 5 3 1
S : $ a $ a $ a $ b $ b $
Array {[6] } est le résultat de L'algorithme de Manacher.
Maintenant, la somme de A[i]/4 l'indice, où '$', d'autre (A[i]+1)/4 pour chaque autre caractère de 1
Ici, $ agit comme un centre pour les sous-chaînes palidromiques de longueur paire et la longueur impaire peut être calculée normalement. La réponse à ce cas est:
0 + 1 + 1 + 2 + 1 + 1 + 0 + 1 + 1 + 1 + 0 = 9 (a,a,aaa,a,b,b,aa,aa,bb).