6

Suppose we are given a string S, and a list of some other strings L.

How can we know if S is a one of all the possible concatenations of L?

For example:

S = "abcdabce"

L = ["abcd", "a", "bc", "e"]

S is "abcd" + "a" + "bc" + "e", then S is a concatenation of L, whereas "ababcecd" is not.

In order to solve this question, I tried to use DFS/backtracking. The pseudo code is as follows:

boolean isConcatenation(S, L) {
    if (L.length == 1 && S == L[0]) return true;
    for (String s: L) {
        if (S.startwith(s)) {
            markAsVisited(s);
            if (isConcatnation(S.exclude(s), L.exclude(s))) 
                return true;
            markAsUnvisited(s);
        }
    }
    return false;
}

However, DFS/backtracking is not a efficient solution. I am curious what is the fastest algorithm to solve this question or if there is any other algorithm to solve it in a faster way. I hope there are algorithms like KMP, which can solve it in O(n) time.

5
  • 1
    by "all the possible concatenations", do you mean concatenations of permutations of the list L?
    – roippi
    Jul 18, 2013 at 19:12
  • @roippi Yes. For example, L=["ab", "c", "d"], "all the possible concatenations" are: [abcd, abdc, cabd, cdab, dabc, dcab]
    – Yifei
    Jul 18, 2013 at 19:19
  • When you say O(n), is n the number of possible permutations of L? Or is it the number of characters in S? If it is the permutations of L, then of course you can. If it is the characters in S, I don't think that's possible. Jul 18, 2013 at 19:29
  • Is L fixed? If so, you can precompile a deterministic finite automaton which should allow an efficient solution. Jul 18, 2013 at 20:25
  • Must L fit S exactly or can it include substrings that can build S and some extra substrings? Jul 18, 2013 at 20:26

7 Answers 7

3

In python:

>>> yes = 'abcdabce'
>>> no = 'ababcecd'
>>> L = ['abcd','a','bc','e']
>>> yes in [''.join(p) for p in itertools.permutations(L)]
True
>>> no in [''.join(p) for p in itertools.permutations(L)]
False

edit: as pointed out, this is n! complex, so is inappropriate for large L. But hey, development time under 10 seconds.

You can instead build your own permutation generator, starting with the basic permutator:

def all_perms(elements):
    if len(elements) <=1:
        yield elements
    else:
        for perm in all_perms(elements[1:]):
            for i in range(len(elements)):
                yield perm[:i] + elements[0:1] + perm[i:]

And then discard branches that you don't care about by tracking what the concatenation of the elements would be and only iterating if it adds up to your target string.

    def all_perms(elements, conc=''):
    ...
            for perm in all_perms(elements[1:], conc + elements[0]):
    ...
                if target.startswith(''.join(conc)):
    ...
1
  • @CapelliC Yes, I always solve things the 'dumb' (but functional) way then optimize. See edit
    – roippi
    Jul 18, 2013 at 20:13
2

A dynamic programming approach would be to work left to right, building up an array A[x] where A[x] is true if the first x characters of the string form one of the possible concatenations of L. You can work out A[n] given earlier A[n] by checking each possible string in the list - if the characters of S up to the nth character match a candidate string of length k and if A[n-k] is true, then you can set A[n] true.

I note that you can use https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm to find the matches you need as input to the dynamic program - the matching costs will be linear in the size of the input string, the total size of all candidate strings, and the number of matches between the input string and candidate strings.

0

i would try the following:

  • find all positions of L_i patterns in S
  • let n=length(S)+1
  • create a graph with n nodes
  • for all L_i positions i: directed edges: node_i --> L_i matches node --> node_{i+length(L_i)}
  • to enable the permutation constrains you have to add some more node/edges to exclude multiple usage of the same pattern
  • now i can ask a new question: is there exists a directed path from 0 to n ?

notes:

  • if there exists a node(0 < i < n) with degree <2 then no match is possible
  • all nodes which have d-=1, d+=1 are part of the permutation
  • bread first or diskstra to look for the solution
0

You can use the Trie data structure. First, construct a trie from strings in L.

Then, for the input string S, search for the S in the trie.

During searching, for every visited node which is an end of one of the words in L, call a new search on the trie (from the root) with remaining (yet unmatched) suffix of S. So, we are using recursion. If you consume all characters of S in that process then you know, that S is a contatenation of some strings from L.

0

I would suggest this solution:

  1. Take an array of size 256 which will store the occurence count of each character in all strings of L. Now try to match that with count of each character of S. If both are unequal then we can confidently say that they cannot form the given character.
  2. If counts are same, Do the following, using KMP algorithm try to find simultaneously each string in L in S. If at any time there is a match we remove that string from L and continue search for other strings in L. If at any time we dont find a match we just print that it cannot be represented. If at the end L is empty we conclude that S indeed is a concatenation of L.

Assuming that L is a set of unique strings.

0

Two Haskell propositions:

There may be some counter examples to this...just for fun...sort L by a custom sort:

import Data.List (sortBy,isInfixOf)

h s l = (concat . sortBy wierd $ l) == s where
  wierd a b | isInfixOf (a ++ b) s = LT
            | isInfixOf (b ++ a) s = GT
            | otherwise            = EQ


More boring...attempt to build S from L:

import Data.List (delete,isPrefixOf)

f s l = g s l [] where
  g str subs result
    | concat result == s = [result]
    | otherwise   = 
        if null str || null subs' 
           then []
           else do sub <- subs'
                   g (drop (length sub) str) (delete sub subs) (result ++ [sub])
   where subs' = filter (flip isPrefixOf str) subs 

Output:

*Main> f "abcdabce" ["abcd", "a", "bc", "e", "abc"]
[["abcd","a","bc","e"],["abcd","abc","e"]]

*Main> h "abcdabce" ["abcd", "a", "bc", "e", "abc"]
False

*Main> h "abcdabce" ["abcd", "a", "bc", "e"]
True 
0

Your algorithm has complexity N^2 (N is the length of list). Let's see in actual C++

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

typedef pair<string::const_iterator, string::const_iterator> stringp;
typedef vector<string> strings;

bool isConcatenation(stringp S, const strings L) {
    for (strings::const_iterator p = L.begin(); p != L.end(); ++p) {
        auto M = mismatch(p->begin(), p->end(), S.first);
        if (M.first == p->end()) {
            if (L.size() == 1)
                return true;
            strings T;
            T.insert(T.end(), L.begin(), p);
            strings::const_iterator v = p;
            T.insert(T.end(), ++v, L.end());
            if (isConcatenation(make_pair(M.second, S.second), T))
                return true;
        }
    }
    return false;
}

Instead of looping on the entire vector, we could sort it, then reduce the search to O(LOG(N)) steps in the optimum case, where all strings start with different chars. The worst case will remain O(N^2).

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.