有趣的字符串算法

Question

给定两个有限的字符串序列，A和B，每个长度为n， 例如：

A1：“kk”，A2：“ka”，A3：“kkk”，A4：“a” 

  B1：“ka”，B2：“kakk”，B3：“ak”，B4：“k” 
  

给出一个有限的索引序列，使得它们对于 A 的集中度 和 B 给出相同的字符串。 允许重复。

在此示例中，我找不到解决方案，但例如如果列表 (1,2,2,4) 是一个解决方案，则 A1 + A2 + A2 + A4 = B1 + B2 + B2 + B4。 在这个例子中只有两个角色，但是已经非常困难了。 事实上，找到一个字符的最短解决方案并不是一件容易的事！

我试着想一些事情......例如，字符串长度的总和必须相等，并且对于第一个和最后一个字符串，我们需要相应的字符。 但没有别的。 我想对于某些字符串来说这是根本不可能的。 有人能想到一个好的算法吗？

编辑：显然，这是 帖子通信问题

没有算法可以决定是否存在这样的问题一个实例是否有解。 如果有的话，停机问题就可以解决。 肮脏的伎俩...

Answer 1

非常棘手的问题，但我会尝试一下。 这更像是一种意识流，而不是答案，提前道歉。

如果我理解正确的话，你会得到 2 个大小相等的字符串序列，A 和 B，索引从 1..n 开始。 然后，您必须找到一个索引序列，使得字符串 A(1)..A(m) 的串联等于字符串 B(1)..B(m) 的串联，其中 m 是索引序列的长度。

我观察到的第一件事是可能有无限多个解决方案。 例如，给定：

A { "x", "xx" }
B {“xx”，“x”}

可能的解决方案是：

{ 1, 2 }
{ 2, 1 }
{ 1, 2, 1, 2 }
{ 1, 2, 2, 1 }
{ 2, 1, 1, 2 }
{ 2, 1, 2, 1 }
{ 1, 2, 1, 2, 1, 2}
...

那么你怎么知道何时停止呢？ 一旦你有了一个解决方案？ 一旦其中一个解决方案是另一个解决方案的超集？

您可以开始的一个地方是从两个集合中取出所有最小公共长度的字符串（在上面的示例中，您将从两个集合中取出“x”，然后搜索共享公共索引的 2 个相等的字符串。然后您可以对下一个尺寸的字符串重复此操作，例如，如果第一组有 3 个长度分别为 1、2 和 3 的字符串，第二组分别有长度为 1、3 和 3 的字符串，则您将采用 的字符串。 length 3。如果你找不到更多的字符串，那么

当你必须开始组合多个字符串时，问题就会变得更加困难，就像我上面的例子一样。强制方法是开始排列两个集合中的所有字符串，当连接时，会产生相同长度的字符串，然后比较它们，在下面的示例中：

A { "ga", "bag", "ac", "a" }
B {“ba”，“g”，“ag”，“gac”}

您将从长度为 2 的序列开始：

A { "ga", "ac" }, B { "ba", "ag" } (索引 1, 3)
A { "bag", "a" }, B { "g", "gac" } （索引 2、4）

比较这些给出 "gaac" 与 "baag" 和 "baga" 与 "ggac"，两者都不是相等，所以没有解。 接下来，我们将寻找长度为 3 的序列：

A { "ga", "bag", "a" }, B { "ba", "g", "gac" } (索引 1, 2, 4)
A { "bag", "ac", "a" }, B { "g", "ag", "gac" } （索引 2, 3, 4）

同样，没有解，所以我们最终得到的序列尺寸 4，我们没有解决方案。

现在它变得更加棘手，因为我们必须开始考虑也许重复一些指数，现在我的大脑正在融化。

我认为在字符串中查找公共子序列可能会有所帮助，然后使用字符串中不匹配的其余部分。 但我不太知道怎么做。

Answer 2

一个非常简单的方法就是使用广度优先搜索之类的东西。 这还有一个优点，即找到的第一个解决方案将具有最小的尺寸。

Answer 3

目前尚不清楚您正在寻找的“解决方案”是什么，最长的解决方案？ 最短的？ 所有解决方案？
由于您允许重复，因此某些输入会有无限多个解决方案，因此我将致力于：

查找固定长度下的所有序列。

以伪代码形式编写，但其方式与 f# 序列表达式非常相似

// assumed true/false functions

let Eq aList bList =  
// eg Eq "ab"::"c" "a" :: "bc" -> true
// Eq {} {} is _false_

let EitherStartsWith aList bList =  
// eg "ab"::"c" "a" :: "b" -> true
// eg "a" "ab" -> true
// {} {} is _true_    

let rec FindMatches A B aList bList level
    = seq {
        if level > 0
            if Eq aList bList
                yield aList
            else if EitherStartsWith aList bList
                Seq.zip3 A B seq {1..} 
                |> Seq.iter (func (a,b,i) -> 
                    yield! FindMatches A B aList::(a,i) bList::(b,i) level - 1) }

let solution (A:seq<string>) (B:seq<string>) length =
    FindMatches A B {} {} length

一些可减少问题的琐碎约束：

1. 第一个选择对必须具有共同的起始部分。
2. 最终的选择对必须有一个共同的结束部分。

基于此我们可以快速消除很多无解的输入

let solution (A:seq<string>) (B:seq<string>) length =
    let starts = {}
    let ends = {}
    Seq.zip3 A B seq {1..} 
    |> Seq.iter(fun (a,b,i) -> 
        if (a.StartsWith(b) or b.StartsWith(a))
            start = starts :: (a,b,i)
        if (a.EndsWith(b) or b.EndsWith(a))
            ends = ends :: (a,b,i))

    if List.is_empty starts || List.is_empty ends
        Seq.empty // no solution
    else
        Seq.map (fun (a,b,i) -> 
            FindMatches A B {} :: (a,i) {} :: (b,i) length - 1)
        starts 
        |> Seq.concat

Answer 4

这是暴力搜索的建议。 首先生成限制为列表长度的数字序列：

[0,0,..]
[1,0,..]
[2,0,..]
[3,0,..]
[0,1,..]
...

数字序列长度决定了找到的任何解决方案中将包含多少个字符串。
然后使用数字作为字符串列表的索引来生成 A 和 B 字符串：

public class FitSequence 
{
    private readonly string[] a;
    private readonly string[] b;

    public FitSequence(string[] a, string[] b)
    {
        this.a = a;
        this.b = b;
    }

    private static string BuildString(string[] source, int[] indexes)
    {
        var s = new StringBuilder();
        for (int i = 0; i < indexes.Length; ++i)
        {
            s.Append(source[indexes[i]]);
        }
        return s.ToString();
    }

    public IEnumerable<int[]> GetSequences(int length)
    {
        foreach (var numberSequence in new NumberSequence(length).GetNumbers(a.Length - 1))
        {
            string a1 = BuildString(a, numberSequence);
            string b1 = BuildString(b, numberSequence);
            if (a1 == b1)
                yield return numberSequence;
        }
    }
}

该算法假设 A 和 B 的长度相等。
我测试了你的示例，

    static void Main(string[] args)
    {
        var a = new[] {"kk", "ka", "kkk", "a"};
        var b = new[] {"ka", "kakk", "ak", "k"};
        for (int i = 0; i < 100; ++i)
            foreach (var sequence in new FitSequence(a, b).GetSequences(i))
            {
                foreach (int x in sequence)
                    Console.Write("{0} ", x);
                Console.WriteLine();
            }
    }

但找不到任何解决方案，尽管它似乎适用于简单的测试。