Python implémente la recherche de la sous-chaîne non répétitive la plus longue pour une chaîne donnée

Cet article présente principalement la méthode de Python pour trouver la sous-chaîne non répétitive la plus longue pour une chaîne donnée, impliquant les compétences de parcours, de tri, de calcul et d'autres opérations connexes de Python pour les chaînes. Les amis dans le besoin peuvent s'y référer

. L'exemple de cet article décrit la méthode permettant de trouver la sous-chaîne non répétitive la plus longue pour une chaîne donnée en Python. Partagez-le avec tout le monde pour votre référence, comme suit :

Question :

Étant donné une chaîne, trouvez la sous-séquence répétitive la plus longue, si la chaîne est composée d'un seul caractère, tel que "aaaaaaaaaaaaa", alors la sortie qui répond aux exigences est une

Idée :

L'idée ici est Les deux sont ceux auxquels je peux penser

(1) Parcourez la chaîne depuis le début, définissez le bit d'indicateur, et lorsque vous constatez qu'il coïncide avec le bit d'indicateur précédent en cours de en revenant en arrière, revenez en arrière et vérifiez si la sous-chaîne est la même que la chaîne précédente ou la sous-chaîne de la chaîne précédente, si elle est la même, la sous-chaîne est enregistrée et le compte est augmenté de 1 jusqu'à ce que le traitement soit terminé. terminé

(2) Utilisez le mécanisme de découpage par fenêtre coulissante pour générer toutes les tranches Ensuite, les statistiques et le traitement utilisent principalement la fonction de tri double

Cet article adopte la deuxième méthode. mise en œuvre :

#!usr/bin/env python
#encoding:utf-8
'''''
__Author__:沂水寒城
功能：给定一个字符串，寻找最长重复子串
'''
from collections import Counter
def slice_window(one_str,w=1):
  '''''
  滑窗函数
  '''
  res_list=[]
  for i in range(0,len(one_str)-w+1):
    res_list.append(one_str[i:i+w])
  return res_list
def main_func(one_str):
  '''''
  主函数
  '''
  all_sub=[]
  for i in range(1,len(one_str)):
    all_sub+=slice_window(one_str,i)
  res_dict={}
  #print Counter(all_sub)
  threshold=Counter(all_sub).most_common(1)[0][1]
  slice_w=Counter(all_sub).most_common(1)[0][0]
  for one in all_sub:
    if one in res_dict:
      res_dict[one]+=1
    else:
      res_dict[one]=1
  sorted_list=sorted(res_dict.items(), key=lambda e:e[1], reverse=True)
  tmp_list=[one for one in sorted_list if one[1]>=threshold]
  tmp_list.sort(lambda x,y:cmp(len(x[0]),len(y[0])),reverse=True)
  #print tmp_list
  print tmp_list[0][0]
if __name__ == '__main__':
  print "脚本之家测试结果："
  one_str='abcabcd'
  two_str='abcabcabd'
  three_str='bbbbbbb'
  main_func(one_str)
  main_func(two_str)
  main_func(three_str)

Les résultats sont les suivants :

Recommandations associées :

Python implémente la méthode de sortie d'un nombre dans l'ordre inverse selon les exigences spécifiées

Python implémente la méthode de saisie de plusieurs lignes dans IDLE

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!