我试图在一串二进制数字中找到一个重复的模式。
例如。0010010010 或 1110111011 = 好的
不是。0100101101 = 坏
字符串长度为 10 位（如上），我猜“模式”的 2 次迭代是最少的。
我开始手动设置程序可以与之匹配的模式“库”，但必须有更好的方法使用算法吗？
搜索让我无处可去 - 我认为我使用的语言和术语不正确..
问问题
4654 次
7 回答
2
相当的挑战。这个功能怎么样？
function findPattern(n) {
var maxlen = parseInt(n.length/2);
NEXT:
for(var i=1; i<=maxlen; ++i) {
var len=0, k=0, prev="", sub;
do {
sub = n.substring(k,k+i);
k+= i;
len = sub.length;
if(len!=i) break;
if(prev.length && sub.length==i && prev!=sub) continue NEXT;
if(!prev.length) prev = sub;
} while(sub.length);
var trail = n.substr(n.length-len);
if(!len || len && trail==n.substr(0,len)) return n.substr(0,i);
}
return false;
}
它甚至适用于具有任何内容的任何长度的字符串。看小提琴
受 Jack's 和 Zim-Zam's answer 的启发，这里是蛮力算法的列表：
var oksubs =
["001","010","011","100","101","110",
"0001","0010","0011","0100","0101","0110","0111",
"1000","1001","1010","1011","1100","1101","1110",
"00000","00001","00011","00101","00110","00111","01000",
"01001","01010","01011","01100","01101","01110","01111",
"10000","10001","10011","10101","10110","10111","11000","11001",
"11010","11011","11100","11101","11110","11111"];
感谢 Jack 的评论，这里有简短而有效的代码：
function findPattern(n) {
var oksubs = [n.substr(0,5),n.substr(0,4),n.substr(0,3)];
for(var i=0; i<oksubs.length; ++i) {
var sub = oksubs[i];
if((sub+sub+sub+sub).substr(0,10)==n) return sub;
}
return false;
}
于 2013-05-10T05:01:57.930 回答
1
我的蛮力方法是：
举例
给定字符串
0010010010：：为 givenString 创建可能的模式列表
0010010010：possiblePatterns = [00, 010, 0010, 00100, 01, 001, 0100, 10, 100]重复它们以制作长度> = 10的字符串
testPattern0 = 0000000000 // 00 00 00 00 00 testPattern1 = 010010010010 // 010 010 010 010 testPattern2 = 001000100010 // 0010 0010 0010 ...并检查...
for each testPattern: if '0010010010' is a substring of testPattern ==> pattern found匹配的字符串之一：
testPattern2: 010010010010 givenString : 0010010010发现模式：
foundPatterns = [010, 001, 100]
如您所见，这可能是一个冗余列表，因为所有模式基本相同，只是移位了。但根据用例，这实际上可能是您想要的。
代码：
function findPatterns(str){
var len = str.length;
var possible_patterns = {}; // save as keys to prevent duplicates
var testPattern;
var foundPatterns = [];
// 1) create collection of possible patterns where:
// 1 < possiblePattern.length <= str.length/2
for(var i = 0; i <= len/2; i++){
for(var j = i+2; j <= len/2; j++){
possible_patterns[str.substring(i, j)] = 0;
}
}
// 2) create testPattern to test against given str where:
// testPattern.length >= str.length
for(var pattern in possible_patterns){
testPattern = new Array(Math.ceil(len/pattern.length)+1).join(pattern);
if(testPattern.indexOf(str) >= 0){
foundPatterns.push(pattern);
}
}
return foundPatterns;
}
==>小提琴
于 2013-05-10T05:08:14.010 回答
1
据我所知，有 62 个长度为 10 => 的模式化二进制字符串2^1 + 2^2 + 2^3 + 2^4 + 2^5。这是一些列出它们并匹配模式字符串的代码：
function binComb (n){
var answer = []
for (var i=0; i<Math.pow(2,n);i++){
var str = i.toString(2)
for (var j=str.length; j<n; j++){
str = "0" + str
}
answer.push(str)
}
return answer
}
function allCycles(){
var answer = {}, cycled = ""
for (var i=1; i<=5; i++){
var arr = binComb(i)
for (var j=0; j<arr.length; j++){
while(cycled.length < 10){
cycled += arr[j]
if (10 - cycled.length < arr[j].length)
cycled += arr[j].substr(0,10 - cycled.length)
}
if (answer[cycled])
answer[cycled].push(arr[j])
else answer[cycled] = [arr[j]]
cycled = ""
}
}
return answer
}
function getPattern (str){
var patterns = allCycles()
if (patterns[str])
return patterns[str]
else return "Pattern not found."
}
输出：
console.log(getPattern("0010010010"))
console.log(getPattern("1110111011"))
console.log(getPattern("0100101101"))
console.log(getPattern("1111111111"))
["001"]
["1110"]
Pattern not found.
["1", "11", "111", "1111", "11111"]
于 2013-05-10T13:31:25.723 回答
1
- 维护一个 2^10 的数组无济于事，因为它不会指示哪些字符串具有重复模式。
要具有重复模式，模式长度只能是 <= 5
可以有长度为 1 的模式。但长度为 5 的模式将覆盖它。[步骤编辑]
如果存在长度为 2 的模式，则始终存在长度为 4 的模式。
从 (1),(2), (3) 和 (4) 中，只需要检查长度为 3,4 和 5 的模式
这意味着如果前三位数字与接下来的三位数字匹配，则继续到字符串结尾，否则中断并转到 7
否则将前四位数字与接下来的四位数字匹配，如果匹配继续到字符串结尾，则中断并转到8
否则将前五位数字与接下来的四位数字匹配，如果匹配继续到字符串结尾，则中断并转到9
如果 6, 7,8 之一为假，则返回失败
于 2013-05-10T05:42:18.197 回答
1
您只有 2^10 个模式，这是一个足够小的数字，您可以预先计算所有有效字符串并将结果存储在 1024 元素布尔数组中；如果字符串有效，则将其转换为整数（例如“0000001111”= 15）并将“true”存储在结果数组索引中。要检查字符串是否有效，请将其转换为整数并在预先计算的布尔数组中查找索引。
如果您的字符串长度超过 10 位，那么您需要更聪明地确定一个字符串是否有效，但由于您只有 1024 个字符串，您不妨对此偷懒。
于 2013-05-10T04:02:22.393 回答
0
在 Python 中（再次）但没有正则表达式：
def is_repeated(text):
'check if the first part of the string is repeated throughout the string'
len_text = len(text)
for rep_len in range(len_text // 2, 0, -1):
reps = (len_text + rep_len) // rep_len
if (text[:rep_len] * reps).startswith(text):
return rep_len # equivalent to boolean True as will not be zero
return 0 # equivalent to boolean False
matchstr = """\
1001110011
1110111011
0010010010
1010101010
1111111111
0100101101
"""
for line in matchstr.split():
print('%r has a repetition length of %i' % (line, is_repeated(line)))
输出：
'1001110011' has a repetition length of 5
'1110111011' has a repetition length of 4
'0010010010' has a repetition length of 3
'1010101010' has a repetition length of 4
'1111111111' has a repetition length of 5
'0100101101' has a repetition length of 0
于 2013-05-10T06:49:02.173 回答
0
这个答案使用 Python 正则表达式来编译 VERBOSE 标志集，该标志集允许带有注释和非重要空格的多行正则表达式。我还在正则表达式中使用命名组。
正则表达式是在 Kodos 工具的帮助下开发的。
正则表达式搜索长度为 5、4、3 重复字符的最长重复字符串。（两个重复的字符是多余的，因为它等于较长的四个；同样，一个重复被五个重复）。
import re
rawstr = r"""
(?P<r5> .{5}) (?P=r5) |
(?P<r4>(?P<_42> .{2}) .{2}) (?P=r4) (?P=_42) |
(?P<r3>(?P<_31> .{1}) .{2}) (?P=r3){2} (?P=_31)
"""
matchstr = """\
1001110011
1110111011
0010010010
1010101010
1111111111
0100101101
"""
for matchobj in re.finditer(rawstr, matchstr, re.VERBOSE):
grp, rep = [(g, r) for g, r in matchobj.groupdict().items()
if g[0] != '_' and r is not None][0]
print('%r is a repetition of %r' % (matchobj.group().strip(), rep))
给出输出：
'1001110011' is a repetition of '10011'
'1110111011' is a repetition of '1110'
'0010010010' is a repetition of '001'
'1010101010' is a repetition of '1010'
'1111111111' is a repetition of '11111'
于 2013-05-10T06:24:17.437 回答