有趣的字符串算法

这个问题很难回答,但我会试试。这更多的是一种意识流,而不是一种答案,提前道歉。

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

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

可能的解决方案有:

{ 2, 1 }

{ 1, 2, 2, 1 }

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

A{“ga”、“bag”、“ac”、“A”}
B{“ba”、“g”、“ag”、“gac”}

A{“袋子”,“A”},B{“g”,“gac”}(索引2,4)

A{“袋子”、“ac”、“A”}、B{“g”、“ag”、“gac”}(索引2、3、4)

同样,没有解,所以我们最终得到大小为4的序列,其中我们没有解。

一个非常简单的方法是使用广度优先搜索。这也有一个优点,即找到的第一个解决方案将具有最小的尺寸。

目前尚不清楚您正在寻找的“解决方案”是什么,最长的解决方案是什么?最短的?所有解决方案?

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

// 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

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

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

数字序列长度决定了在找到的任何解中有多少个字符串。 然后使用这些数字作为字符串列表的索引来生成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;
        }
    }
}

    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();
            }
    }