香草Python（剽窃检查器）如何检测的话，是相同的，在原来的句子？

Question

我想用香草Python做一个简单的抄袭检查器。在python中不使用外部libs

因此，如果相同的单词连续出现4次以上，我想打印输出（连续相同的单词）

我试过下面的代码。 但它显示了每一个相同的词，即使这些词不连续相同少于4次。。你知道吗

b1='i guess that osaka city is just a souless city it is obviously weird'.split(' ')
a1='all of the meaning less time i guess thinking that osaka city is huge a souless city it is obviously weird'.split(' ')

# expected_result
#['that osaka city is','a souless city it is obviously weird']



temp1=[]
for b in b1:
    for a in a1:
        if b == a :
            temp1.append(b)

        if len(temp1)>=4:
            print(' '.join(temp1))
        else:
            print('==')

然而结果是

i guess that osaka city city is is a souless city city it is is obviousl
y
i guess that osaka city city is is a souless city city it is is obviousl
y
i guess that osaka city city is is a souless city city it is is obviousl
y weird

还有。。。这就是我想做的

#### Example; 

# INPUT
a = 'Hello my name is Osaka, today I learned about Mochi
is just a shit of snowman'
b = 'Hello my name is Kidney, bullshit, mann yesterday I learned about Katzu is just a shit of snowman'
# EXPECTED OUTPUT
['Hello my name is','is just a shit of snowman']

Answer 1

你把a1中的每个单词和b1中的每个单词进行比较。所有匹配的单词都被添加到temp1。但是你从不检查单词的序列。这就是为什么你会得到a1中的所有单词。你知道吗

这里有一个比较序列的简单方法：取a1和b1中的每两个索引，并在字符匹配时尝试前进。如果找到4个或更多匹配字符，请输出字符：

B='i guess that osaka city is just a souless city it is obviously weird'.split(' ')
A='all of the meaning less time i guess thinking that osaka city is huge a souless city it is obviously weird'.split(' ')

for i in range(len(A)):
    for j in range(len(B)):
        m, n = i, j
        while m<len(A) and n<len(B) and A[m] == B[n]:
            m, n = m+1, n+1
        if m-i >= 4:
            print((i, j), A[i:m])

如果你承认itertools在“Vanilla Python”（我知道VanillaJS，但我不确定“Vanilla Python”是什么意思），你可以这样写：

import itertools
for i, j in itertools.product(range(len(A)), range(len(B))):
    L = [u for u,v in itertools.takewhile(lambda u_v : u_v[0]==u_v[1], zip(A[i:], B[j:]))]
    if len(L)>=4:
        print((i,j), L)

输出

(9, 2) ['that', 'osaka', 'city', 'is']
(14, 7) ['a', 'souless', 'city', 'it', 'is', 'obviously', 'weird']
(15, 8) ['souless', 'city', 'it', 'is', 'obviously', 'weird']
(16, 9) ['city', 'it', 'is', 'obviously', 'weird']
(17, 10) ['it', 'is', 'obviously', 'weird']

你会得到一些垃圾，因为如果['a', 'souless', 'city', 'it', 'is', 'obviously', 'weird']是从(14, 7)开始的最长匹配，我们知道从(15, 8)开始的列表也会是一个匹配。让我们添加一个exclude集来删除这些子列表：

exclude = set()
for i in range(len(A)):
    for j in range(len(B)):
        if (i,j) in exclude:
            exclude.remove((i,j))
            continue
        m, n = i, j
        while m<len(A) and n<len(B) and A[m] == B[n]:
            m, n = m+1, n+1
        if m-i >= 4:
            print((i, j), A[i:m])
            exclude.update((i+k, j+k) for k in range(1, m-i))
            print ("exclude = ", exclude)

输出：

(9, 2) ['that', 'osaka', 'city', 'is']
exclude =  {(12, 5), (11, 4), (10, 3)}
(14, 7) ['a', 'souless', 'city', 'it', 'is', 'obviously', 'weird']
exclude =  {(20, 13), (16, 9), (17, 10), (15, 8), (19, 12), (18, 11)}

这种方法可行，但速度很慢：时间复杂度为O（| A |*| B |*最长匹配）。可以使用以下方法省去一些检查：为列表| B |构建一个字典word -> [positions]，以避免对B中的每个A单词重新检查所有索引：

positions_by_word_in_B = {}
for j, word in enumerate(B):
    positions_by_word_in_B.setdefault(word, []).append(j)

输出：

{'i': [0], 'guess': [1], 'that': [2], 'osaka': [3], 'city': [4, 9], 'is': [5, 11], 'just': [6], 'a': [7], 'souless': [8], 'it': [10], 'obviously': [12], 'weird'
: [13]}

主回路变为：

for i in range(len(A)):
    for j in positions_by_word_in_B.get(A[i], []):
        # all positions of A[i] in B, maybe none

时间复杂度降到O（| B |+| A |*| B |*最长匹配中A的一个单词的最大出现次数）。也可以在len（A）-4而不是len（A）-1处停止迭代。你知道吗

如果你想检查一大堆文件是否有抄袭，这可能还是太慢了。你知道吗