regex - 是否可以为任意字符串的字谜生成(紧凑)正则表达式？

Question

问题:用任何语言编写一个程序，给定一个字符串，生成一个与输入字符串的任何字谜匹配的正则表达式。对于所有大于某个长度 N 的正则表达式，正则表达式必须短于列出所有可能的字谜的“蛮力”解决方案，其中列出了由“|”分隔的所有可能的字谜，并且正则表达式的长度应该随着输入字符串的增长而“缓慢”增长(理想情况下是线性的) ，但可能是 n ln n)。

你能做到吗？我已经尝试过了，但我的尝试远未成功，以至于我开始怀疑这是否可能。我问的唯一原因是我以为我在另一个网站上看到了一个解决方案，但是很多无意义的谷歌搜索未能第二次发现它。

Answer 1

我认为此 javascript 代码将根据您的规范工作。正则表达式的长度将随着输入的长度线性增加。它生成一个正则表达式，它使用正向前瞻来匹配输入字符串的字谜。正则表达式的先行部分确保所有字符都出现在测试输入字符串中，忽略它们的顺序，匹配部分确保测试输入字符串的长度与输入字符串的长度(正则表达式的构建)相同。

function anagramRegexGenerator(input) {
    var lookaheadPart = '';
    var matchingPart = '^';
    var positiveLookaheadPrefix='(?=';
    var positiveLookaheadSuffix=')';
    var inputCharacterFrequencyMap = {}
    for ( var i = 0; i< input.length; i++ )
    {
        if (!inputCharacterFrequencyMap[input[i]]) {
            inputCharacterFrequencyMap[input[i]] = 1
        } else {
            ++inputCharacterFrequencyMap[input[i]];
        }
    }
    for ( var j in inputCharacterFrequencyMap) {
        lookaheadPart += positiveLookaheadPrefix;
        for (var k = 0; k< inputCharacterFrequencyMap[j]; k++) {
            lookaheadPart += '.*';
            if (j == ' ') {
                lookaheadPart += '\\s';
            } else {
                lookaheadPart += j;
            }
            matchingPart += '.';
        }
        lookaheadPart += positiveLookaheadSuffix;
    }
    matchingPart += '$';
    return lookaheadPart + matchingPart;
}

示例输入和输出如下

anagramRegexGenerator('aaadaaccc')
//generates the following string.
"(?=.*a.*a.*a.*a.*a)(?=.*d)(?=.*c.*c.*c)^.........$"
anagramRegexGenerator('abcdef ghij'); 
//generates the following string.
"(?=.*a)(?=.*b)(?=.*c)(?=.*d)(?=.*e)(?=.*f)(?=.*\s)(?=.*g)(?=.*h)(?=.*i)(?
=.*j)^...........$" 
//test run returns true
/(?=.*a)(?=.*b)(?=.*c)(?=.*d)(?=.*e)(?=.*f)(?=.*\s)(?=.*g)(?=.*h)(?=.*i)(?
=.*j)^...........$/.test('acdbefghij ')
//or using the RegExp object
//this returns true
new RegExp(anagramRegexGenerator('abcdef ghij')).test('acdbefghij ') 
//this returns false
new RegExp(anagramRegexGenerator('abcdef ghij')).test('acdbefghijj')