Calculates the maximum public substring of two strings

background

There has been little application of algorithms. Recently, I saw some typical algorithms and wanted to practice. I wanted to see how annoying they are. In fact, the discovery algorithms have certain routines, which are generally not imagined temporarily. They are mostly based on some existing classical algorithm knowledge and data structure. In other words, if you haven't touched some playing methods before, it's still difficult for you to think of them temporarily in a short time. This is a bit similar to the project experience. If you have ever done a CRM system, you will be much easier next time you encounter it. If you challenge a system you have never encountered, you can only eat it with your existing knowledge.

Calculates the maximum common substring of two strings

This is often encountered. Give two strings of arbitrary length and output the maximum public string. For example, if you enter ABCDEF and cdef, you will output cdef.

Solution

The double-layer loop is adopted, the pointer moves to record all substrings, and finally the maximum length substring is taken. The temporary queue is used to store the character elements that match successfully in the loop process, starting from the first element of the two strings.

Sketch Map

Compare from element 0

When the pointer of string a does not move, B looks back in turn, finds at least the same character, and presses the same character into the temporary queue.

The first matching element appears

When a matching element appears, both strings move back one element for comparison.

Match interrupted

If the previous matching is successful, and the characters are different in the back, it will be terminated.

Reset index, circular match

The pointer of string B moves backward, the pointer of string a is reset, and the above steps are recursive.

Sample code

The following example records all substrings. If you only want to output the maximum substring, you need to change the logic, define a maximum substring, and then compare it with the substring calculated by cycle, and take the maximum length of both.

advantage

Pointer movement will not produce redundant temporary strings during the loop. If it is a substring scheme, efficiency needs to be considered.

The above is the whole content of this article. I hope the content of this article can bring some help to your study or work. At the same time, I also hope to support a lot of programming tips!