Help in a string question.

6 лет назад, # |

Auto comment: topic has been updated by K_B_C_S (previous revision, new revision, compare).

→ Ответить

6 лет назад, # |

← Rev. 3 →

First of all sort the list strings in decreasing order according to length and the check for every string one by one and check two conditions ,

If string is not found in master string then return "false"
If string is found in master string then (replace it with *) them from master string.

If all the string satisfied condition 2nd return "True"

→ Ответить

6 лет назад, # ^ |

can you explain your approach with "monkeyoumonkeyuo" as master string and {"monkey", "you"} as list of string?

→ Ответить

6 лет назад, # ^ |

← Rev. 3 →

first search monkey , monkey is in master string then replace monkey (replace which monkey which does not contain any other string) from master string the master string becomes (monkeyou******uo).

Then search you in master string it is found in master string) so answer is TRUE.

UPD : don't delete , replace it with ******

→ Ответить

6 лет назад, # ^ |

How will you decide that a string doesn't contain any other string?

→ Ответить

6 лет назад, # ^ |

This can be check but time limit exceeded.

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

This is wrong. Simple example: baaba, {"a", "baab"}. After finding and removing a, the string will become baba, and the last one string is left, however, it could be found if we searched for baab first.

→ Ответить

6 лет назад, # ^ |

I already says that sort the strings in decreasing order according to length.

→ Ответить

6 лет назад, # ^ |

Yes, missed that. However, it is still wrong: abcbc, {bc, ab}. Removing bc yields a**bc, and ab is left, however searching in the reverse order would find both ab and bc.

→ Ответить

6 лет назад, # ^ |

Yes, You are right but what about this one

→ Ответить

6 лет назад, # ^ |

I've already responed in that thread that my initial approach was wrong. The list needs to be topologically sorted before searching.

→ Ответить

6 лет назад, # ^ |

What's wrong with my This approach

→ Ответить

6 лет назад, # ^ |

Nothing's wrong, but how do you choose the ranges such that they do not interleave?

→ Ответить

6 лет назад, # ^ |

connect all range of (i)th string of (i + 1)th string ranges according to condition that (two ranges connect if they do not overlap.

then range of (i + 1)th string to (i + 2)th string range and so on ...

and at last find a path if we can reach from 1st string to the last string..

if there is a path then answer is "YES" otherwise "NO"

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

Replacing with asterisks instead of deleting does not fix the problem.

→ Ответить

6 лет назад, # |

← Rev. 6 →

Perform topological sorting of the list. We assume a directed edge between items (a, b) if there is a suffix of a which is a prefix of b. We do a regular toposort of this graph. Then, we reverse the order.
Calculate hashes of strings in the list and store them. Also calculate hashes of prefixes of the master string.
Search for each string using sliding window technique, from the start of the master string. Track characters of the master string which belong to the found items. When encountering such character, start over from the next one. If an item is not found, return false.
All items are found, return true.

Steps 1-2 are essentially Rabin-Karp algorithm. Could be replaced with any string search algorithm of your choice.

→ Ответить

6 лет назад, # ^ |

Master string contains other characters as well.

on the step 4, if you came to the end of the string, and the set is nonempty, you start from the next character. Why is it working?

→ Ответить

6 лет назад, # ^ |

We assume that the first character doesn't belong to any string from the list, Therefore, we skip it.

→ Ответить

6 лет назад, # ^ |

You are skipping first character this i understood.

I am asking, are you reseting the set or not for next iteration?

How will it work for master string "monkeyouxzmonkeyuo" and {"monkey", "you"}

In this example skipping starting character only can't solve right?

You have to skip 'x', 'z' also.

→ Ответить

6 лет назад, # ^ |

You can skip several characters in a row. In you case it won't skip any, because monkey and you are found one after the other. But, for example, in monkeyxxxyou, we will skip three characters (xxx).

→ Ответить

6 лет назад, # ^ |

No, 'y' is common.

This is the thing, how is your approach skipping xxx in monkeyxxxyou?

→ Ответить

6 лет назад, # ^ |

← Rev. 4 →

Haha, yes, it seems that approach is wrong, it fails on the same example I've provided for starboy_jb. When one string has a prefix that is a suffix of another the order of which string to search for first matters. I'll update the comment.

→ Ответить