Java classic problem: even a string is a loopback displacement to each other

This time I bring you questions that often appear in the interview of Java programmers who judge whether even a string is circular rotation. I have given you answers in two ways. I hope it can help you.

In general, it is a written test or direct computer operation. The question type is generally: if the character in string s can get another string t after cyclic movement at any position, then s is called the circular rotation of T.

A string s is a circular rotation of a string t if it matches when the characters are circularly shifted by any number of positions; e.g.,ACTGACG is a circular shift of TGACGAC,and vice versa. Detecting this condition is important in the study of genomic sequences. Write a program that checks whether two given strings s and t are circular.

As for the solution, I give two ways here: solution 1: divide s into left and right parts, and then make s' = right + left to traverse all cases. If it is a loopback string, there will be s' = t.

Solution 2: (ingenious)

The above are two basic and fast solutions. About this problem, I'll show you a very detailed solution to the loopback displacement of judgment string:

If the character in string s can get another string t after cyclic movement at any position, s is called the loop displacement of T. For example, actgacg is a loop displacement of tgacgac, and vice versa. It is very important to determine this condition in the study of genome sequence. Write an algorithm to check whether two given strings S and T are loop displacement to each other.

This is an exercise I saw in the algorithm (Fourth Edition). The first idea at that time was to traverse the string t, decompose the string t into two substrings from different index positions, exchange the order and splice, and then compare it with S. the algorithm is as follows:

Later, I looked at the answer and suggested that it could be done with one line of code. At that time, I thought it was impossible, so I gave it up. When I started learning this book again today, I saw this problem again and suddenly had an idea. The code is as follows:

Explanation: if the strings S and T are loop modifications to each other, s can be decomposed into "ab" and t can be decomposed into "Ba". After t is spliced with itself, it is "Baba", which obviously contains s. This idea is ingenious. Of course, I think the efficiency of the algorithm has not been improved.

Why is everyone confused about this classic java problem? The main reason is the problem-solving idea:

It's easy to think of complex "loop displacement". If you think wrong, the problem will be complicated. Let's look at the classic misunderstanding and finally figure out the solution in the future.

The title description is very simple: if another string t can be obtained after the character with heavy string s is cyclically moved to any position, then s will become the circular rotation of S. for example, omit... Problem: please write a program to check whether two given strings S and T are each other's circular rotation. Tip: only one line of code is required to judge the condition

When I saw the title, my mind was full of double cycles, cursor movement, various I, J, K... As a result, I couldn't stand such a hint at that time and decided to look at the answer

The answer is this

At first glance, it seems that you can... Immediately despise your various cursor loops I, K... (although the underlying layer may also be various cyclic cursors I, K, it is obviously easier to use the base classes implemented by others directly...)

But I also found that I didn't understand the concat function of string class and various overloads of indexof

The following is a description of the JDK document

This issue has been clearly explained in the last article. If you have any questions about it, you can leave a message at the bottom of this article.