You can solve this problem by the following technique:
Proc 1: Take any word W in the file
Find all strings S(k) which are formed by concatenating k words in the file
and is a prefix of W. [A word can repeat multiple times in different places]
As you can see, number of words in S(k) will certainly be greater than or
equal to S(k+1). Further, S(k+1) can be formed using S(k).
Algo1: You run the Proc 1 finding S(k)s for each k >= 2 until you either
1. find some count(S(k)) = 0 where you are not able to find other words
which can be used to form the current word
2. if some word in S(k) is equivalent to W, then you have a candidate word W
which can be formed using other words.
Here goes the pseudo code for the program :
*vs arr; *// a vector of strings containing the word that I am searching
for.
// The function takes as input an integer pos. This "pos" is the index of
the string in arr for which we are finding whether the string arr[pos] can
be formed using other words.
*bool canForm(int pos) {*
bool *tmp, *tmp1;
int l = arr[pos].size();
tmp = new bool[l+1];
tmp1 = new bool[l+1];
for(i,0,l+1) tmp1[i] = tmp[i] = false;
tmp[0] = true;
while (true) {
bool atleastOne = false;
for(i,0,l+1) tmp1[i] = false;
for(i,0,l) {
if (tmp[i] == true) {
for(j,0,arr.size()) {
if (pos != j) {
if (l - i >= arr[j].size()) {
bool match = true;
for(k,0,arr[j].size()) {
if (arr[j][k] != arr[pos][i+k]) {
match = false;
break;
}
}
if (match) {
tmp1[i + arr[j].size()] = true;
atleastOne = true;
if (i + arr[j].size() == l) return true;
}
}
}
}
}
}
bool *t = tmp;
tmp = tmp1;
tmp1 = t;
if (!atleastOne) return false;
}
// never comes
return false;
}
worst case time complexity : If there are n words and the maximum length
string is of length l, then O(n^2 * l ^ 2)
--deepak
On Tue, May 20, 2008 at 11:26 PM, [EMAIL PROTECTED] <
[EMAIL PROTECTED]> wrote:
>
> Regular expressions ?
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
