查找字符串中最短的重复模式

Question

我想知道是否有办法在 Octave / matlab 中进行模式匹配？我知道 Maple 10 有执行此操作的命令，但不确定我需要在 Octave / Matlab 中做什么。因此，如果数字是 12341234123412341234，则模式匹配将是 1234。我试图找到 最短的模式，在重复后生成整个字符串 。

请注意：数字（只会使用数字）不会这么简单。另外，我不会提前知道模式（这就是我想要找到的）。请参阅下面的 Maple 10 example，其中显示模式无法提前获知，但命令会找到模式。

Maple 10 模式匹配示例：

ns:=convert(12341234123412341234,string);

             ns := "12341234123412341234"

StringTools:-PrimitiveRoot(ns);

             "1234"

如何在 Octave / Matlab 中执行此操作？ Ps：我正在使用 Octave 3.8.1

Answer 1

我不确定这是否可以用正则表达式来完成。这是一个脚本，可以在重复单词 pattern.

的情况下执行您需要的操作

它循环遍历名为 str 的字符串中的字符，试图匹配另一个名为 pattern 的字符串。如果匹配失败，pattern 字符串将根据需要进行扩展。

编辑：我使代码更紧凑。

str = 'lullabylullabylullaby';

pattern = str(1);
matchingState = false;
sPtr = 1;
pPtr = 1;

while sPtr <= length(str)
     if str(sPtr) == pattern(pPtr) %// if match succeeds, keep looping through pattern string
            matchingState = true;
            pPtr = pPtr + 1;
            pPtr = mod(pPtr-1,length(pattern)) + 1;
     else                          %// if match fails, extend pattern string and start again
            if matchingState
                sPtr = sPtr - 1;   %// don't change str index when transitioning out of matching state
            end  
            matchingState = false;
            pattern = str(1:sPtr);
            pPtr = 1;
     end

     sPtr = sPtr + 1;

end

display(pattern);

输出为：

pattern =

lullaby

注：

这不允许在出现的 pattern 字符串之间使用任意分隔符。例如，如果 str = 'lullaby1lullaby2lullaby1lullaby2';，则

pattern =

lullaby1lullaby2

这也允许 pattern 在循环中途结束而不改变结果。例如，str = 'lullaby1lullaby2lullaby1'; 仍然会导致

pattern =

lullaby1lullaby2

要解决此问题，您可以添加行

if pPtr ~= length(pattern)
    pattern = str;
end

Answer 2

要找到重复生成整个字符串的最短模式，您可以使用正则表达式，如下所示：

result = regexp(str, '^(.+?)(?=*$)', 'match');

一些例子：

>> str = '12341234123412341234';
>> result = regexp(str, '^(.+?)(?=*$)', 'match')
result = 
    '1234'

>> str = '1234123412341234123';
>> result = regexp(str, '^(.+?)(?=*$)', 'match')
result = 
    '1234123412341234123'

>> str = 'lullabylullaby';
>> result = regexp(str, '^(.+?)(?=*$)', 'match')
result = 
    'lullaby'

>> str = 'lullaby1lullaby2lullaby1lullaby2';
>> result = regexp(str, '^(.+?)(?=*$)', 'match')
result = 
    'lullaby1lullaby2'

Answer 3

另一种做法如下：

判断字符串长度，求出字符串长度值的所有可能因素
对于每个可能的因子长度，重塑字符串并检查对于重复的子串

要找到所有可能的因素，请参阅 this SO 上的解决方案。下一步可以通过多种方式执行，但我在一个简单的循环中实现它，从最小的因子长度开始。

function repeat = repeats_in_string(str);
ns = numel(str);
nf = find(rem(ns, 1:ns) == 0);
for ii=1:numel(nf)
    repeat = str(1:nf(ii));
    if all(ismember(reshape(str,nf(ii),[])',repeat)); 
        break;
    end
end

Answer 4

这道题是对您解决问题方法的一次很好的罗夏墨迹测试。我将添加一个信号工程解决方案，它应该很简单，因为信号应该是完全重复的，假设成立：找到重复生成整个字符串的最短模式。

下面的str输入函数的实际上是一个浮点数的列向量，不是字符串，原来的字符串已经用str2num(str2mat(str)')转换了：

function res=findshortestrepel(str);
[~,ii] = max(fft(str-mean(str)));
res = str(1:round(numel(str)/(ii-1)));

我进行了一个小测试，将其与 regexp 解决方案进行比较，发现它总体上更快（蓝色方块），尽管有些不一致，并且前提是您不考虑转换所需的时间将字符串转换为浮点数向量（绿色方块）。但是我没有进一步追求这个（没有打破记录）：

秒

查找字符串中最短的重复模式

Finding the shortest repetitive pattern in a string

regex

matlab

pattern-matching

octave

maple