0

In order to de-crypt a message, I need to first find the key. From the given information, I find the key is part of the string:

str = "251220825122082"

We can easily get that the key should be "2512208" since the key is supposed to be repeatedly used in encrypting a message. However, I tried many methods and got the answer "25122082", which adds another 2 in the end, but it's just another beginning of the key.

The method I have tried:

  1. regex: String repeated = str.replaceAll("(.+?)\\1+", "$1");
  2. LRS Java

These two provide the same answer("25122082").

Can anyone help me with this problem?

Thank you!

Suraj Rao
  • 29,388
  • 11
  • 94
  • 103
Bella Wang
  • 21
  • 1
  • 9
  • Possible duplicate of: http://stackoverflow.com/questions/10355103/finding-the-longest-repeated-substring – Tim Biegeleisen Jan 16 '17 at 04:13
  • 1
    `replaceAll` is doing exactly what it's supposed to do: it replaces 25122082512208 with 2512208. There's still a "2" left at the end of the string, which it doesn't replace. Here, since you are trying to extract information out of a string, `replaceAll` is the wrong tool for the job. Use `find` to search for a regex, and `group` to extract the capture group. `replaceAll` is for replacing portions of an input string with other strings and leaving the rest of the input string alone. That's not what you're trying to do here. – ajb Jan 16 '17 at 04:14
  • How do you know for sure that 2512208 is the key and not 25122082? – Nick Ziebert Jan 16 '17 at 04:20
  • @TimBiegeleisen Not duplicate, using that method I cannot get right answer. Even using this online demo, I cannot get right answer either. https://daniel-hug.github.io/longest-repeated-substring/ – Bella Wang Jan 16 '17 at 04:21
  • @NickZiebert because the key is repeated. If 25122082 is the key, than what's the repeated pattern? If the key is not long enough to encrypt the message, it should loop back from the beginning. – Bella Wang Jan 16 '17 at 04:25
  • Oh, gotcha. I assumed you were looking at lines and lines of numbers and finding the pattern with most occurrences. – Nick Ziebert Jan 16 '17 at 04:29
  • Looks like something that requires a dynamic programming algorithm. – David Choweller Jan 16 '17 at 04:31
  • @ajb Awesome! Solved this question using find() and group(). Thank you! – Bella Wang Jan 16 '17 at 04:41

1 Answers1

0

Thanks to @ajb, solved this question by using find() and group().

    String str = "251220825122082";
    Pattern p = Pattern.compile("(.+?)\\1+");
    Matcher m = p.matcher(str);
    while (m.find()) {
        String repeated = m.group(1);
        System.out.println(repeated);
    }

Output: 2512208

Bella Wang
  • 21
  • 1
  • 9
  • What I meant was that you can say `m.group(1)` to get the contents of the first group (which means the same as `\\1` in the regex or `$1` in the replacement string). `m.group()` gives you the entire matched string, but `m.group(1)` gives you exactly the key you need. You don't need another `replaceAll` after that. – ajb Jan 16 '17 at 05:12
  • Thank you! But what if the key is "5122082", how do I find it? – Bella Wang Jan 16 '17 at 14:48
  • If the input string is `str` above, and the "longest consecutive repeated substring" is the key, then it's ambiguous. Both 2512208 and 5122082 meet the criteria, and both are equally long. If you have a rule that would make it clear that 5122082 is the key (such as, the _last_ substring in the file is chosen in case of a tie), then there may be a way to adjust the code to follow the rule. If you don't have a rule, then there is no solution--there's no way to decide between the two. – ajb Jan 17 '17 at 04:42
  • This approach could only get "first repeated string". For `str = "22512208225122082"`, this approach gets "2" 4 times, instead of the right answer "25122082" – John Apr 28 '18 at 07:15