Anagram_of_a_word.py

Question

我正在 Python 环境中工作。 我有一个宏观任务要解决，但现在我有一个巨大的问题要解决微观任务：在text中找到word的“B-anagram”，但是“B-anagram”MUST包括一个角色。

一个例子是文本“the-astronautis-t&kingpict/res.”和单词“artos”。 我想从函数中收到的“B 字谜”是：

• “astro”包含“astro”+“n” -> “astro”是“artos”的字谜词，“n”是加号。
• “strona”包含“stroa”+“n” -> “stroa”是“artos”的字谜，“n”是加号。

加号字符可以是文本中单词字符之间的任何字符，因此在此示例中，对于单词“sitt”，“B 字谜”是“tis-t”，其中“-”是加号字符。

有人可以澄清我的想法吗，我已经挣扎了好几天了:-(.

我尝试过使用单词长度，从文本中单词第一个字母的第一个索引开始搜索，并向左和向右搜索 len(word)+1，但我一直得到错误的结果。 我也尝试使用 set(text)-set(word) 但这样当我有类似的东西时： 文本“pythonyinncc”和单词“yinc”由于设置，“B-anagram”“yinnc”不会返回。 我无法导入任何库。

我的最终代码使用 set。

def cerca_quasi_anagrammi（testo，parola）：

def ordina_parola(p):
    return ''.join(sorted(p))

def genera_anagrammi(parola):
    if len(parola) <= 1:
        return [parola]
    else:
        anagrammi = []
        for perm in genera_anagrammi(parola[1:]):
            for i in range(len(perm) + 1):
                anagrammi.append(perm[:i] + parola[0] + perm[i:])
        return anagrammi

parola_ordinata = ordina_parola(parola)
anagrammi = genera_anagrammi(parola)
risultati = set()

for anagramma in anagrammi:
    for posizione in range(len(anagramma) + 1):
        for carattere_spurio in set(testo) - set(anagramma):
            nuova_sequenza = anagramma[:posizione] + carattere_spurio + anagramma[posizione:]
            if nuova_sequenza in testo:
                risultati.add(nuova_sequenza)

for i in range(len(testo) - len(parola) + 1):
    sottostringa = testo[i:i + len(parola)]
    if ordina_parola(sottostringa) == parola_ordinata:
        if i > 0:
            anagramma_precedente = testo[i - 1] + sottostringa
            risultati.add(anagramma_precedente)
        if i + len(parola) < len(testo):
            anagramma_successivo = sottostringa + testo[i + len(parola)]
            risultati.add(anagramma_successivo)

return list(risultati)

Answer 1

您可以像这样检查“n+1”字谜：

def is_anagram1(sub, word):
    d = {}
    x = False

    for c in word:
        d[c] = d.get(c, 0) + 1

    for c in sub:
        if c in d:
            if d[c] == 1:
                d.pop(c)
            else:
                d[c] -= 1
        elif x:
            return False
        else:
            x = True

    return not d

这个想法是为一个单词构建一个符号频率字典

symbol: num-of-occurrences

，并且对于子字符串中的每个符号，要么减少频率字典中的值，要么设置一个标志

x

说“这是一个额外的符号”。最后，freq 应该为空，并且应该正好有一个额外的字母。

一旦完成，剩下的就简单了：

def find(text, word):
    size = len(word) + 1

    for i in range(len(text) - size + 1):
        sub = text[i:i + size]
        if is_anagram1(sub, word):
            print(sub)


find('the-astronautis- trxaso -- rtraso', 'astro')

打印

-astro
astron
strona
trxaso
rtraso

这里还有优化的空间，例如，您可以预先计算一次 freq 字典，然后将其传递出去。

Answer 2

我问了 chatGPT 并给了我这个：

def is_strict_b_anagram(word, candidate):
    """Check if the candidate string is a strict B-anagram of the word."""
    if len(candidate) != len(word) + 1:
        return False
    
    for char in word:
        if char in candidate:
            candidate = candidate.replace(char, '', 1)
        else:
            return False
    return True

def find_strict_b_anagrams(word, text):
    """Find all strict B-anagrams of 'word' that exist as a substring in 'text'."""
    b_anagrams = []
    word_length = len(word)
    
    for i in range(len(text) - word_length):
        substring = text[i:i + word_length + 1]
        if is_strict_b_anagram(word, substring):
            b_anagrams.append(substring)
    
    return b_anagrams

# Test the function with the provided example
test_word = "artos"
test_text = "the-astronautis-t&kingpict/res."

# Test the modified function with the provided example
find_strict_b_anagrams(test_word, test_text)