Tagged Questions

10
votes
3answers
703 views

Square Subsequence

A string is called a square string if it can be obtained by concatenating two copies of the same string. For example, "abab", "aa" are square strings, while "aaa", "abba" are not. Given a string, how ...
8
votes
1answer
2k views

how to find the number of distinct subsequences of a string?

Here is another spoj problem that asks how to find the number of distinct subsequences of a string ? For example, Input AAA ABCDEFG CODECRAFT Output 4 128 496 How can I solve ...
8
votes
3answers
301 views

Longest Subsequence with all occurences of a character at 1 place

In a sequence S of n characters; each character may occur many times in the sequence. You want to find the longest subsequence of S where all occurrences of the same character are together in ...
5
votes
1answer
633 views

String distance, transpositions only [duplicate]

Possible Duplicate: Counting the swaps required to convert one permutation into another I'm looking for an algorithm that would count some kind of string distance where only allowed ...
4
votes
4answers
360 views

O(n^2) (or O(n^2lg(n)) ?)algorithm to calculate the longest common subsequence (LCS) of two 'ring' string

This is a problem appeared in today's Pacific NW Region Programming Contest during which no one solved it. It is problem B and the complete problem set is here: ...
3
votes
1answer
180 views

A problem about algorithm of string, dp, graph or sth else

problem is following. about "nice" 1) "ab" is nice 2) A is nice => "a"+A+"b" is nice 3) A and B are nice => A+B is nice about "~" 1) "ab"~"ab" 2) A~B => "a"+A+"b"~"a"+B+"b" 3) A~B and C~D => ...
2
votes
1answer
55 views

Given a phrase without spaces add spaces to make proper sentence

This is what I've in mind, but it's O(n^2): For ex: Input is "Thisisawesome", we need to check if adding the current character makes the older found set any longer and meaningful. But in order to see ...
1
vote
2answers
77 views

Why does this DP solution for longest common subsequence work correctly?

Concerning the longest common subsequence problem, the basic algorithm as presented in all online resources is clear to me. This algorithm is described here: What I am not clear is the algorithm ...
1
vote
1answer
145 views

Number of equal subsequences of two strings S1 and S2 with the last char of S1 matched

Given two strings S1 & S2 of different length, what is the efficient approach to find the number of equal subsequences of both S1 and S2 with last char of S1 matched. e.g) S1 = ayb ...
0
votes
2answers
62 views

Suffix tries vs dynamic programming for string algorithms

It seems that many difficult string algorithms can be solved both using suffix tries(trees) and Dynamic Programming. But I am not sure which approach is best to use and when. Additionally which ...
0
votes
0answers
40 views

Dynamic Programming/LCS.Why is it defined in terms of suffix

I am reading about the DP version of the longest common substring from wiki: It uses the formula: LCS(p, q) = LCS(p - 1, q - 1) + 1 if X[p] == Y[q] ELSE LCS(p, q) = 0 This is defined as the ...
0
votes
2answers
57 views

parse text into valid sentence

I have a doubt about how to parse any text into valid sentence. Suppose a text is given iamjhamb and parse into i am jhamb My approach: I solved this using Dynamic programmnig, Make an ...