Ho difficoltà a trovare un algoritmo che corrisponda (o non riesca a far corrispondere) una sottostringa di una stringa a un suffisso da un elenco di suffissi. I successi che sto riscontrando riguardano gli alberi di suffisso e gli array di suffissi, ma non sono proprio quello che sto cercando.
Il mio problema particolare è un nome host completo, possibilmente malformato, e sto tentando di abbinare il suffisso fornito dalla lista dei suffissi vietati pubblicati di Mozilla. Come esempio concreto, dato w.x.y.z.example.com , ho bisogno di identificarlo come hostname w , dominio example.com e sapere che example.com è dominio valido.
Come esempio degenerativo, potrei dover prendere example.com e sapere che è un dominio senza host e che corrispondere a *.com sarebbe sbagliato. E i casi negativi peggiorano solo quando si calcolano suffissi come pvt.k12.ma.us , nasushiobara.tochigi.jp , 公司.cn e السعودیة .
L'eventuale applicazione sarà la corrispondenza del nome host DNS nei certificati X509. Di qui la ragione per cui ci possono essere input malformati da miscredenti.
Penso che questo algoritmo dovrebbe essere eseguito in m log n . log n per ogni ricerca nell'elenco [ordinato] di suffissi e m per ogni etichetta DNS.
Penso che potrebbe essere il caso di non vedere la foresta tra gli alberi. Qualcuno sa di un algoritmo efficiente per la corrispondenza delle sottostringhe da un elenco di suffissi?