python - 在更大的字符串中查找嵌套序列

任务是找到一个数字序列，这个序列可以被某个数字转置，也可以被倒过来转置，嵌套在另一个相等或更大的数字集合中。输入来自文本文件。如果该数字是按原样找到的，或者是转置的，则输出找到该数字的起始索引；如果该数字是反转的，或者是转置的，则输出该数字所在的起始索引；如果该数字是反转的，则输出索引后接反转的。
示例-如果要查找的数字是67654，则可以找到45432（向下移动2），或32345（反向移动）或54567（向上移动2）

Input
67654
14676545
43234545679
905
#

第一行是要搜索的内容（67654），其余行是要搜索的内容。

Output
3
7
10 inverted
14 inverted

我的想法是建立一个数字列表，如果要查找的数字与倒转的数字之间存在差异。例如，67654将列出一个列表[-1，1，1，1]然后，我将循环遍历字符串的每个数字，通过使用滑动窗口检查它是否出现我也做了同样的倒转。

diffs = [int(name[x]) - int(name[x + 1]) for x in range(0, len(name) - 1)] #name stores the fist line of input
invertedName = ''.join([str(9-int(x)) for x in name])

currDiffs = []
for i in range(len(name)-1):
    currDiffs.append(int(piece[i]) - int(piece[i+1])) #piece is the string being searched

for i in range(len(name)- 1, len(piece) - 1):
    currDiffs.pop(0)
    currDiffs.append(int(piece[i]) - int(piece[i+1]))
    Compare(diffs,currDiffs) # check if theyre the same

这样做我的答案，我发现自己得到的答案几乎都是错误的。如果有任何关于如何修正我的方法或者如果有什么问题的建议，我将不胜感激。

最佳答案

这并不是最有效的解决方案，但似乎是可行的：

def find_diffs(inval):
    inval = map(int, inval)
    plain = [i - inval[0] for i in inval[1:]]
    return plain, [-i for i in plain]


def check(inval, against):
    inval_diff, _ = find_diffs(inval)
    print against, inval
    for i in range(0, len(against) - len(inval) + 1):
        test, inverted_test = find_diffs(against[i: i + len(inval)])
        if test == inval_diff:
            print i
        elif test == inval_inverted_diff:
            print i, "inverted"

inval = '67654'

check(inval, '14676545')
check(inval, '43234545679')
check(inval, '1467654543234545679905')

输出

14676545 67654
2
43234545679 67654
1 inverted
5 inverted
1467654543234545679905 67654
2
6
9 inverted
13 inverted

那这是干什么？
这里的想法是，对于给定的输入，我们可以将输入转换为一个值列表，其中第一个值总是0，其余的值是它和第一个值之间的差。例如：

1234 => 0, 1, 2, 3
5463 => 0, -1, 1, -2
6667 => 0, 0, 0, 1

我们同样可以对任何数字进行比较。为了比较，我们从我们比较的数字中取前n个数，其中n是源数的长度。
在最后一个例子中，源代码是67654，所以长度是5against号码是146765453234545679905，所以前5位是14676。
使用上述差分公式：

67654 => 0, 1, 0, -1, -2
14676 => 0, 3, 5, 6, 5

所以这不匹配继续执行此操作，滑动against数字的起始索引，直到耗尽列表。
唯一要考虑的是倒转对于反向检查，只需将差分列表中的每个数字乘以-1即可偏移量无关紧要，因为它是恒定的。
如果需要偏移值，事情会稍微复杂一些。

关于python - 在更大的字符串中查找嵌套序列，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/18940895/