CN115982310B - Chain table generation method with verification function and electronic equipment - Google Patents

Abstract

This application is applicable to the field of computer technology, and provides a linked list generation method with its own verification function and electronic equipment. The method includes: generating a plurality of special positive sequence suffixes about the original character string according to an array of character types; The above special positive sequence suffixes are inductively sorted to determine the first order; the first linked list for fingerprint verification is generated according to each special positive sequence suffix; a plurality of second suffixes about the second character type are inductively sorted according to the first linked list, Determining the second order; generating a second linked list for fingerprint verification according to each second suffix; generating a suffix linked list corresponding to the original character string according to the second linked list of each second character type. Using the method of this embodiment, the verification process can be integrated in the construction process, so the constructed suffix linked list does not need to be verified separately, and the verification efficiency of the suffix linked list can be improved.

Description

Method and electronic device for generating linked list with self-contained verification function

technical field

The embodiments of the present application belong to the field of computer technology, and in particular relate to a method for generating a linked list with a verification function and an electronic device.

Background technique

The suffix linked list is a single linked list linked according to the order information of the suffixes in the linked list. Each suffix in the suffix linked list points to a suffix with a larger or smaller lexicographical order, so that it can The relation implements the reading of character data. Since the suffix linked list is a data structure that can perform full-text indexing based on suffixes, the suffix linked list is often used in the field of data compression. When using the suffix linked list for data compression, the correctness of the suffix linked list directly affects the correctness and compression efficiency of the compression algorithm, so how to ensure the correctness of the suffix linked list becomes the key to the data compression process.

In the prior art, there are mainly the following two methods for verifying the correctness of the suffix linked list. First, traverse the suffix linked list according to the pointing relationship of each suffix, and read the adjacent suffixes of the suffix linked list from the string for comparison. Second, after decompressing the suffix linked list, compare the decompressed character string with the original character string. However, the first verification method takes a lot of time, and the second verification method cannot guarantee a high compression ratio. Therefore, it is difficult in the prior art to realize fast verification of the suffix linked list while ensuring a high compression rate.

Contents of the invention

In view of this, the embodiment of the present application provides a linked list generation method with its own verification function, which is used to integrate the verification process of the suffix linked list in the construction process of the linked list, so that the constructed suffix linked list does not need to be verified separately.

The first aspect of the embodiment of the present application provides a method for generating a linked list with its own verification function, including:

Generate a plurality of special positive sequence suffixes about the original string according to the character type array; the character type array is generated according to the character type corresponding to each character in the original string; the first suffix is the character of the first character of the suffix The type is a suffix of a special positive sequence type; the character type of each character is determined by the character size between each character and its adjacent characters;

performing inductive sorting on the multiple special positive sequence suffixes, and determining the first order of the multiple special positive sequence suffixes;

Generate a first linked list for fingerprint verification according to the order of each of the special positive sequence suffixes in the first order and the character position of the first character of the suffix in the original character string;

According to the first linked list, a plurality of second suffixes related to the second character type are inductively sorted to determine the second order of the plurality of second suffixes; according to each of the second suffixes in the second order Order and the character position of the first character of the suffix in the original character string to generate a second linked list for fingerprint verification;

A suffix linked list corresponding to the original character string is generated according to the second linked list of each of the second character types.

The second aspect of the embodiment of the present application provides a linked list generation device with its own verification function, including:

The special positive sequence suffix determination module is used to generate a plurality of special positive sequence suffixes about the original character string according to the character type array; the character type array is generated according to the character type corresponding to each character in the original character string; the The special positive sequence suffix is the character type of the first character of the suffix is the suffix of the special positive sequence type; the character type of each character is determined by the character size between each character and its adjacent characters;

A first order determination module, configured to inductively sort the plurality of special positive sequence suffixes, and determine the first order of the plurality of special positive sequence suffixes;

The first linked list generation module is used to generate the first list for fingerprint verification according to the order of each of the special positive sequence suffixes in the first order and the character position of the first character of the suffix in the original string. linked list;

The second linked list generation module is used to inductively sort a plurality of second suffixes related to the second character type according to the first linked list, and determine the second order of the plurality of second suffixes; according to each of the second suffixes In the order in the second order and the character position of the first character of the suffix in the original character string, generate a second linked list for fingerprint verification;

A suffix linked list generating module, configured to generate a suffix linked list corresponding to the original character string according to the second linked list of each of the second character types.

The third aspect of the embodiments of the present application provides a terminal device, including a memory, a processor, and a computer program stored in the memory and operable on the processor, when the processor executes the computer program Realize the linked list generation method with built-in verification function as described in the first aspect above.

The fourth aspect of the embodiments of the present application provides a computer-readable storage medium, the computer-readable storage medium stores a computer program, and when the computer program is executed by a processor, the self-contained Linked list generation method for validation functions.

The fifth aspect of the embodiments of the present application provides a computer program product, which, when running on a computer, causes the computer to execute the linked list generation method with its own verification function described in the first aspect above.

Compared with the prior art, the embodiment of the present application has the following advantages:

In the embodiment of the present application, the electronic device generates the first linked list for fingerprint verification by determining a plurality of special positive sequence suffixes and inductively sorting the multiple special positive sequence suffixes. After the first linked list is generated, the electronic device may sort the plurality of second suffixes of the second character type based on the first linked list to generate a second linked list for fingerprint verification. Through the second linked list, the electronic device can construct a suffix linked list corresponding to the original character string. In the embodiment of the present application, since both the first linked list and the second linked list can be used for fingerprint verification, the verification process of the suffix linked list is integrated in the construction process of the suffix linked list. Therefore, the method for generating the suffix linked list provided in this embodiment can directly verify the correctness of the generated suffix linked list, and can improve the verification efficiency of the suffix linked list.

Description of drawings

In order to illustrate the technical solutions in the embodiments of the present application more clearly, the following briefly introduces the drawings required for the embodiments or the description of the prior art. Apparently, the drawings in the following description are only some embodiments of the present application, and those skilled in the art can obtain other drawings according to these drawings without creative efforts.

Fig. 1 is a schematic diagram of the storage structure of the suffix array and the suffix linked list of the character string X provided by the embodiment of the present application;

Fig. 2 is a schematic diagram of the elements of the suffix array of the character string X provided by the embodiment of the present application;

Fig. 3 is a schematic structural diagram of two kinds of suffix linked lists of character string X provided by the embodiment of the present application;

FIG. 4 is a schematic diagram of a method for generating a linked list with a verification function provided in an embodiment of the present application;

FIG. 5 is a schematic diagram of a possible implementation of S404 provided in the embodiment of the present application;

Fig. 6 is a schematic diagram of a linked list generating device with its own verification function provided by the embodiment of the present application;

FIG. 7 is a schematic diagram of a terminal device provided by an embodiment of the present application.

Detailed ways

In the following description, specific details such as specific system structures and technologies are presented for the purpose of illustration rather than limitation, so as to thoroughly understand the embodiments of the present application. It will be apparent, however, to one skilled in the art that the present application may be practiced in other embodiments without these specific details. In other instances, detailed descriptions of well-known systems, devices, circuits, and methods are omitted so as not to obscure the description of the present application with unnecessary detail.

The suffix linked list is a suffix singly linked list linked in ascending or descending order based on string suffixes. A linked list of suffixes can be constructed by storing the positions of the suffixes linked by a given string in ascending or descending order in an integer array. Each suffix in the constructed suffix list can point to the next suffix with a larger or smaller lexicographic order. The suffix linked list is mainly used in the field of data compression. The preparatory stage of the factorization of the famous compression algorithm LZ77 is to construct a suffix single linked list by linking the given strings in ascending or descending order. Both the suffix array and the suffix linked list are suffix-based full-text index data structures, both of which store the sequence information of string suffixes. The suffix array belongs to the sequential storage structure, and the suffix linked list belongs to the linked storage structure. For a given input string X[1,n] with an input length of n, the string X can contain n suffixes of different lengths, for example, use suf(X, i) to represent X from the i-th character to the end The suffix of , that is, the string X[i, n], i∈[1,n]. For example, if the string X[1,12]="bbcbbabbcbba", the length of the string X can be 12, and the string X can contain 12 suffixes with different lengths. suf(X,2) can represent the suffix from the second character to the end in the string X, that is, suf(X,2)=bcbbabbcbba. The suffix linked list of the string X is a single linked list based on the integer array Y[0, n], Y[0] is the head of the linked list, Y[0] can point to the largest or smallest suffix in the lexicographic order in the suffix linked list, and the remaining elements Y[i] holds the starting position of the next suffix larger or smaller than the suffix suf(X,i), if there is no next suffix larger or smaller than the suffix suf(X,i), the element Y[i] It can point to the head of the linked list Y[0]. Therefore, the suffix linked list of X is a suffix index of an array-based linked storage structure.

The correctness of the suffix linked list directly determines the correctness and compression efficiency of the LZ77 compression algorithm. At present, there are roughly two methods for verifying the correctness of the suffix linked list as follows.

The first verification method is to read the corresponding suffixes from the original string X according to the positions of the adjacent suffixes in the suffix list by traversing the suffix list for comparison, so as to verify the correctness of the suffix list. The first verification method involves a large amount of memory random reading and writing, so the verification time is high.

The second method is to decompress the compressed string generated based on the suffix linked list, and compare the decompressed and restored string with the original string. If the two are consistent, it means that the suffix linked list is probably correct. In the second method, if very few suffixes in the suffix list are in the wrong order, the correct original string may also be recovered, but the suffix list containing the wrong suffix order will cause the compression rate to decrease. Therefore, in the application scenario where the correctness of the linked list needs to be strictly verified, the first method is usually adopted, but it takes a lot of time to verify the correctness of the suffix linked list through the first verification method. An ideal method for verifying the correctness of the suffix linked list should not occupy too much memory space, and at the same time have faster speed and higher accuracy.

The technical solutions of the present application are illustrated below through specific examples.

First, nouns that may be involved in the embodiments of the present application are described here.

String X: A character array X[1, n] consisting of n characters X[1]...X[n]. The character set of X can be represented by Σ. Among them, the dictionary order (dictionary order), also known as the alphabetical order (alphabetical order), originally intended to represent the order of English words in the dictionary, in the computer field, it is extended to two arbitrary characters determined according to the order of English words in the dictionary string size relationship.

Character type: The characters in the string X are divided into two types: L and S. If the character X[i] satisfies X[i]<X[i+1], or satisfies X[i]=X[i+1] and X[i+1] is an S-type character, the character X[i] It can be an S type character (also known as a positive sequence character), otherwise the character X[i] is an L type character (also known as a reverse sequence character), where 1≤i≤n-1. Further, if X[i-1] is a character of type L, and X [i] is a character of type S, then X[i] is of type S* (also known as a special positive sequence character). Among them, the S* type is a subtype of the S type character. In particular, the ending character X[n] can be an S* type character.

Suffix type: The type of suffix is determined by the character type of the first character of the suffix, so the suffix can be divided into two types: L and S, where the S* type suffix is a subset of the S type suffix.

Preceding character: The preceding character of the suffix X[i, n] can be X[i-1].

Prefix and suffix: The prefix and suffix of the suffix X[i, n] can be the suffix X[i-1,n].

Suffix array (SA): The suffix array of string X is an integer array with a length of n. The suffix array can be expressed as SA(X)[1, n]. The suffix array can be stored in ascending order of suffixes from left to right. The starting position of multiple suffixes.

Ascending suffix linked list ψ: an array-based singly linked list with a length of n+1, linking suffixes in ascending lexicographical order to obtain a suffix linked list ψ. Among them, ψ[0] can be the head of the suffix list ψ, and ψ[0] can point to the smallest suffix of the string X. ψ[SA[n]] is the tail of the suffix list ψ, and ψ[SA[n]] can point to the head of the list ψ[0]. Other linked list nodes in the suffix linked list ψ can point to the start position of the next suffix larger than it. Further, the linked list ψ _L can represent an ascending single linked list of L-type suffixes, and the linked list ψ _L can be generated by linking the L-type suffixes to the L-type positions in ascending order. In the embodiment of the present application, the linked list ψ _L may also be called a reverse type suffix ascending single linked list. The table ψ _S can represent a single-linked list of S-type suffixes in ascending order, and the linked list ψ _S can be generated by linking S-type suffixes to S-type positions in ascending order. In the embodiment of the present application, the linked list ψ _S may also be called a positive sequence type suffix ascending single linked list. The linked list ψ _S* can represent a single linked list of S* type suffixes in ascending order, and the linked list ψ _S* can be generated by linking the S* type suffixes to the S* type positions in ascending order. In the embodiment of the present application, the linked list ψ _S* may also be called a special positive sequence type suffix ascending single linked list.

Descending suffix linked list φ: an array-based singly linked list with a length of n+1, linking the suffixes in descending lexicographical order can obtain a suffix linked list φ. Wherein, φ[0] may be the head of the suffix list φ, and φ[0] may point to the largest suffix in the string X. φ[SA[1]] can be the tail of the suffix list φ, and φ[SA[1]] can point to the head of the list φ[0]. Other linked list nodes in the suffix linked list φ can point to the start position of the next suffix smaller than it. Further, the linked list φ _L can represent a single linked list of L-type suffixes in descending order, where the linked list φ _L can be generated by linking multiple L-type suffixes to the link positions of the L-type suffixes in descending order. In the embodiment of the present application, the linked list φ _L may also be called a reverse type suffix descending single linked list. The linked list φ _S can represent a single linked list of S-type suffixes in descending order, where the linked list φ _S can be generated by linking multiple S-type suffixes to the link positions of the S-type suffixes in descending order. In the embodiment of the present application, the linked list φ _S may also be referred to as a positive sequence type suffix descending single linked list. The linked list φ _S* can represent a single linked list in descending order of S* type suffixes, wherein the linked list φ _S* can be generated by linking multiple S* type suffixes to the link positions of S* type suffixes in descending order. In the embodiment of the present application, the linked list φ _S* can also be called a special positive sequence type suffix descending single linked list.

The inductive sorting process of the suffix linked list: the first step is to sort the S* type suffixes, calculate and generate the linked list ψ _S* ; the second step, traverse the linked list ψ _S* , inductively deduce the order of multiple L type suffixes, and calculate and generate the linked list φ _L ; the third step is to traverse the linked list φ _L , inductively deduce the order of multiple S-type suffixes, and calculate and generate the linked list φ _S . Wherein, inductive sorting may be in-place sorting. In the process of constructing the suffix linked list, the suffix array SA and the different types of suffix linked lists φ and ψ all reuse the storage space of the same array Y. The element type of each element in the array Y is in one-to-one correspondence with the character type of each character in the string X. For example, if X[i] is a character of type L, then Y[i] is also an array element of type L.

Bucket linked list: The singly linked list formed by linking L-type suffixes starting with the same character c can be called the L-type bucket linked list of c. A singly linked list formed by linking S-type suffixes starting with the same character c can be called an S-type bucket list of c. For the convenience of expression, the arrays Lbkts[|Σ|] and Lbkte[|Σ|] can be used to record the start and end pointers of each L-type bucket list, and the arrays Sbkts[|Σ|] and Sbkte[|Σ|] can be used respectively Record the start and end pointers of each S-type bucket list.

Karp-Rabin fingerprint function: The Karp-Rabin fingerprint function can calculate the fingerprint (ie: hash value) of a string or sequence, and the error probability of the string or sequence can be controlled by adjusting the parameters of the formula in the fingerprint calculation function. The Karp-Rabin fingerprint function has iterative and combined properties, and the fingerprints of substrings or sequences of any length can be iteratively calculated through formulas (1-1) to (1-3). Among them, FP(a,b) can represent the fingerprint of a substring or sequence from a to b elements, and the parameters δ and K are both prime numbers and δ<K. In particular, the larger δ and K are, the lower the error probability is.

FP(0, -1) = 0 (1-1)

FP(0, p) = (FP(0,p-1)*δ + x[p]) mod K (1-2)

FP(p, q) = (FP(0,q) - fp(0, p-1)*δ ^q-p+1 ) mod K (1-3)

It should be noted that in this embodiment of the application, the ascending or descending order may be determined by the lexicographical order of each suffix. Multiple positive-order suffixes are linked in descending lexicographical order, and a descending positive-order linked list can be generated. Multiple positive order suffixes are linked in ascending lexicographical order to generate an ascending positive order linked list. Multiple reverse suffixes are linked in descending lexicographical order, and a descending reverse linked list can be generated. Multiple reverse suffixes are linked in ascending lexicographical order to generate an ascending reverse linked list.

Take the string X[1,12]="bbcbbabbcbba" as an example to explain the specific content of the above nouns:

As shown in FIG. 1 , it is a schematic diagram of the storage structure of the suffix array and the suffix linked list of the character string X.

Referring to FIG. 1 , the specific character types of each character in the character string X are shown. For example, in the string X, since the lexicographic order of the character X[02]=b is smaller than the lexicographic order of the character X[03]=c, the character type of the character X[02]=b can be S type; in the string X Since the lexicographic order of the character X[01]=b is the same as that of the character X[02]=b, the character type of the character X[01]=b can be determined by the character type of the character X[02]=b. And because the character type S of character X[02], so the character type of character X[01]=b can be S type.

Referring to FIG. 1 , it shows the storage structure of the suffix array of the character string X. Wherein, the suffix array SA(X) of the character string X may be an integer array with a length of n, and the array may store the start positions of multiple sorted suffixes of X. For example, SA[01]=12 can save the starting position 12 of the lexicographically smallest suffix in the string X, which can be composed of a character X[12]=a; SA[12]=03 can save the string The starting position 03 of the largest suffix in X (suf(X, 03)=X[03, 12]=cbbabbcbba).

As shown in FIG. 2 , it is a schematic diagram of the elements of the suffix array of the character string X provided in the embodiment of the present application. Fig. 2 shows the suffix corresponding to each element of the suffix array SA(X) of the character string X. Wherein, the serial number in FIG. 2 may indicate which element of SA(X), and may also be understood as the lexicographic order or order of the suffix corresponding to the element. For example, the second element SA[02]=06, the corresponding suffix can be X[06, 12]=abbcbba, and its order in the suffix of X can be 2.

As shown in FIG. 3 , it is a schematic structural diagram of two kinds of suffix linked lists of character string X provided in the embodiment of the present application. Wherein, the suffix linked list of the string X may include an ascending suffix linked list ψ(X) and a descending suffix linked list φ(X). The ascending suffix list ψ(X) and the descending suffix list φ(X) can be integer arrays with a length of n+1. Figure 3 shows the complete link order of each element in the ascending suffix list ψ(X) and the descending suffix list φ(X). When traversing the suffix linked list, the electronic device can traverse the entire linked list from the head of the suffix linked list, and the tail of the suffix linked list points to the position of the head of the linked list according to the convention. In the suffix list, suffixes with the same first character can be linked together to form a bucket list, and the bucket list formed by suffixes with the same first character can include L-type bucket list and S-type bucket list. For example, the suffixes starting with the character b are linked together to form a bucket list of the character b, which can be composed of an L-type bucket list with the character b as the first character and an S-type bucket list with the character b as the first character.

See (a) in Figure 3, which is a schematic structural diagram of the ascending suffix list ψ(X) of the string X. Among them, the ascending suffix linked list ψ(X) can be formed by sequentially linking the head of the linked list, the S-type bucket list of character a, the L-type bucket list of character b, the S-type bucket list of character b, and the L-type bucket list of character c. In the ascending suffix list ψ(X), ψ[0] can be the head of the ascending suffix list ψ(X), and ψ[0] can point to the suffix position 12 of the smallest suffix suf(X, 12) of the string X . ψ[03] can be the tail of the linked list ψ(X) in ascending order, and ψ[03] can point to the head of the linked list ψ[0]. In the ascending suffix linked list ψ(X), the position i other than the head and tail of the linked list can store the suffix position of the next suffix larger than the lexicographical order of the suffix suf(X, i). For example, the next suffix whose lexicographic order is greater than suf(X, 04) is the suffix suf(X, 07), so in the ascending suffix list ψ(X), ψ[04] can point to ψ[07], that is, ψ[04 ]=07.

See (b) in Figure 3, which is a schematic structural diagram of the descending suffix list φ(X) of the character string X. Among them, the descending suffix linked list φ(X) can be sequentially linked by the head of the linked list, the L-type bucket list of character c, the S-type bucket list of character b, the L-type bucket list of character b, and the S-type bucket list of character a. In the descending suffix list φ(X), φ[0] can be the head of the descending suffix list φ(X), and φ[0] can point to the suffix position 03 of the largest suffix suf(X, 03) of the string X. φ[12] can be the tail of the linked list φ(X) in descending order, and φ[12] can point to the head of the linked list φ[0]. In the descending suffix linked list φ(X), the position i other than the head and tail of the linked list can store the suffix position of the next suffix smaller than the lexicographical order of the suffix suf(X, i). For example, the next suffix whose lexicographical order is smaller than suf(X, 04) is the suffix suf(X, 10), so in the descending suffix list φ(X), φ[04] can point to φ[10], that is, φ[04 ]=10.

The technical solutions of the present application are illustrated below through specific examples.

Referring to FIG. 4 , it shows a schematic diagram of a method for generating a linked list with its own verification function provided by the embodiment of the present application. In this embodiment, the execution subject of the method for generating the linked list is an electronic device, and the electronic device can be: Smartphones, computer equipment, servers and other devices capable of data processing. Specifically, the following steps may be included:

S401. Generate a plurality of special positive sequence suffixes on the original character string according to the character type array; the character type array is generated according to the character type corresponding to each character in the original character string; the first suffix is the first character of the suffix The character type of is the suffix of the special positive sequence type; the character type of each character is determined by the character size between each character and its adjacent characters;

In the embodiment of the present application, when the electronic device needs to compress the original character string through the compression algorithm LZ77 factorization algorithm, the electronic device can first generate a suffix linked list corresponding to the original character string based on the original character string. When the electronic device constructs a suffix linked list corresponding to an original character string based on the original character string, it may first acquire a character type array corresponding to the original character string. According to the obtained character type array corresponding to the original string, the electronic device can generate multiple suffixes whose first character is a special positive sequence type, that is, the electronic device can generate multiple special positive sequence suffixes based on the character type array. Wherein, the character type array may be generated according to the character type corresponding to each character in the original character string. The character type information of each character in the original string can be included in the string array. Wherein, the character size between each character and its adjacent characters can be determined by the lexicographical size between each character and its adjacent characters. For example, the lexicographic order of character a is less than character b, then character a is less than character b.

In this embodiment, the original character string may contain a plurality of different types of characters, such as special forward-order characters and reverse-order characters. Multiple suffixes can be generated based on multiple character electronics in the original string. The suffix of the original string may be a string composed of multiple characters between the beginning of the character at any position in the original string and the end character of the original string. For example, if the length of an original string X = "bbcbbabbcbba" is 12, the suffix of the string X can be multiple characters from any position i (1≤i≤12) to the end position 12 in the string X A string consisting of the first character of the suffix can be the first character of the suffix. For example, in the suffix suf(X,10)=bba of the above character string X, its first character can be b. In the embodiment of the present application, for descriptions of character types and suffix types, refer to the description of terms in the specification, and details are not repeated here.

In the embodiment of the present application, the electronic device may scan the original character string and sequentially compare the size relationship between each character in the original character string and its adjacent characters, so as to determine the character type of each character in the original character string. After determining the character type of each character in the original character string, its character type can be recorded in the array t. Wherein, the array t recording the character type of each character in the original character string can become a character type array. For example, the type of each character in the character string X in FIG. 1 can be stored in the type array t, and the electronic device can determine the character type of each character in the character string X through the contents of the term description part in the manual. That is, the electronic device can determine the type of X[i] by comparing the size and type of each character X[i] in the character string X with its successor character X[i+1]. For example, since the successor character of the character b at the first position of the string X is also b, and the character type of the successor b is S type, the character b at the first position of the string X can be a positive sequence character; The character b at the second position of X is smaller than its successor character c, so the character at the second position of the string X can be a positive sequence character; the character a at the sixth position of the string X is a positive sequence character, and its predecessor b is Characters in reverse order, so the character a at the 6th position of the string X can be a special positive sequence character; the character a at the 12th position of the string X can be a special positive sequence character by convention; among them, the special positive sequence character also belongs to A positive sequence character is a special type of positive sequence characters. In this application example, the electronic device can record the character type of each character in the string X in the array t by using 1 to represent the forward sequence character and 0 to represent the reverse sequence character, and generate the character type array t corresponding to the string X. Therefore, the character type array t of the string X can be t=110001110001. According to the character type array t, the electronic device can determine multiple special positive sequence suffixes of the character string X, that is, the electronic device can determine suf(X, 06)=X[06,12]=abbcbba and suf(X, 12)=X[ 12]=a is a special positive sequence suffix.

S402. Perform inductive sorting on the multiple special positive sequence suffixes, and determine the first sequence of the multiple special positive sequence suffixes;

In the embodiment of this application, after the electronic device generates multiple special positive sequence suffixes on the original character string based on the character type array, it can sort the generated multiple special positive sequence suffixes through a divide-and-conquer recursive method, thereby obtaining multiple positive sequence suffixes. recursive layer. Based on the obtained multiple recursive layers, the electronic device can obtain the first order of multiple special positive sequence suffixes through an inductive sorting method.

In this application, since the divide-and-conquer recursive algorithm decomposes the original problem into multiple sub-problems, the decomposed sub-problems are independent of each other and have the same form as the original problem. By recursively solving the decomposed sub-problems, the solution of each sub-problem is obtained, and finally the solution of each sub-problem is combined to obtain the solution of the original problem. Therefore, the multiple recursive layers obtained by the divide-and-conquer recursive algorithm may contain some special positive sequence suffixes. According to the order of some special positive sequence suffixes in each recursive layer, the first order of multiple special positive sequence suffixes of the original string can be obtained by inductively sorting each recursive layer.

S403. Generate a first linked list for fingerprint verification according to the order of each special positive sequence suffix in the first sequence and the character position of the first character of the suffix in the original character string;

In the embodiment of the present application, after the electronic device determines the first order of the multiple special positive sequence suffixes of the original character string, it can determine the first character of the suffixes of the multiple special positive sequence suffixes in the original character string according to the character type array. character position. According to the order of each special positive sequence suffix in the first sequence and the character position of the first character of each special positive sequence suffix in the original character string, the electronic device generates the first linked list. Wherein, since the suffix linked list may be composed of multiple nodes, each node may include a data field for storing the suffix itself and a pointer field for storing pointers. Therefore, the electronic device can determine the position of the special positive sequence suffix in the first linked list based on the character position of the first character of the special positive sequence suffix, and the order of the special positive sequence suffix in the first sequence can determine the first linked list. The pointers to each special positive sequence suffix in . The first linked list generated by the electronic device can be used for fingerprint verification.

In the embodiment of the present application, in the process of generating the first linked list according to the order of each special positive sequence suffix in the first sequence and the character position of the first character of each special positive sequence suffix in the original string, the electronic device can The first fingerprints of multiple special positive sequence suffixes are calculated by a fingerprint function. Since the first fingerprint value can be obtained by the electronic device by calculating the sequence of multiple special positive sequence suffixes through the fingerprint function, the first fingerprint value can be used to describe the first sequence of multiple special positive sequence suffixes when generating the first linked list .

In the embodiment of this application, since the electronic device generates the first fingerprint value according to multiple special positive sequence suffixes when generating the first linked list, and the first fingerprint value can be used to describe the multiple special positive sequence values when generating the first linked list. First order of suffixes. Therefore, through the suffix linked list construction method provided by the embodiment of the present application to generate the suffix linked list, the electronic device can determine whether the suffix linked list is correct by comparing whether the first fingerprint value and the second fingerprint value are equal after the suffix linked list is generated. Therefore, through the method adopted in this embodiment, the electronic device can directly verify the correctness of the suffix linked list according to the first fingerprint value, which can improve the efficiency of verifying the correctness of the suffix linked list.

In another implementation, when the electronic device generates the first linked list based on the first order of each special positive-sequence suffix, the first sequence of the multiple special positive-sequence suffixes can be firstly set to The positions are stored in a special positive-order suffix array in ascending order of the first order. Wherein, the special positive sequence suffix array can store the start positions of multiple special positive sequence suffixes on the original string in ascending order from left to right according to the first order of the special positive sequence suffixes. After the electronic device generates the special positive sequence suffix array, it can determine the character positions of multiple special type characters in the original string by scanning the character type array. According to the character position of each special type character in the original character string, the electronic device can determine the character position of the first character of the suffix of each special positive sequence suffix in the special positive sequence suffix array.

In this embodiment of the application, after the first character of the suffix of each special positive sequence suffix, the electronic device can sequentially scan the array of special positive sequence suffixes from right to left, and sequentially scan multiple special positive sequence suffixes according to the special The descending order of the positive-order suffixes in the first order is written into the corresponding temporary positions of each special positive-order suffix to generate a temporary linked list. In the process of writing each special positive sequence suffix into the temporary location in descending order in the first sequence, the electronic device can iteratively calculate the sequence of multiple special positive sequence suffixes through a fingerprint function to generate the first mobile fingerprint. Wherein, the temporary position of each special positive sequence suffix may be the left adjacent position of the first character of the suffix of each special positive sequence suffix in the original character string. Since the first mobile fingerprint value is generated when the electronic device writes multiple special positive sequence suffixes into the temporary location in descending order in the first sequence, the first mobile fingerprint may contain multiple special positive sequence suffixes. Descending order information.

In the embodiment of the present application, since the special forward-sequence character is a forward-sequence character whose predecessor is a reverse-sequence character, the left neighbor of the character position corresponding to the special forward-sequence character may be the position of the reverse-sequence character. Therefore, after the electronic device writes multiple special positive-order suffixes into the temporary location in descending order and generates a temporary linked list, it can scan the array of special positive-order suffixes from right to left, sequentially write the multiple special positive-order suffixes A sequential ascending order, linked from the temporary position into the special forward suffix position, to generate the first linked list. In the process of writing each special positive sequence suffix to the position of the special positive sequence suffix in ascending order in the first sequence, the electronic device can iteratively calculate the sequence of multiple special positive sequence suffixes through the fingerprint function to generate the first link fingerprint. Wherein, the special positive sequence suffix position of each special positive sequence suffix may be the character position of the first character of the suffix of each special positive sequence suffix in the original string. Since the first link fingerprint value is generated when the electronic device writes multiple special positive sequence suffixes into the special positive sequence suffix positions in ascending order in the first sequence, the first link fingerprint may contain multiple special positive sequence suffixes. Ascending order information for ordinal suffix.

In this embodiment of the application, when the electronic device sequentially links multiple special positive sequence suffixes from the temporary position to the special positive sequence suffix position in the ascending order of the first sequence, the electronic device can also link the special positive sequence suffixes according to the The first character of the suffix generates multiple special positive sequence bucket linked lists. Wherein, the special positive sequence bucket linked list may be a single linked list formed by linking multiple special positive sequence suffixes with the same initial character of the suffix. For example, a singly linked list formed by linking multiple special positive sequence suffixes starting with the same character c can be called a special positive sequence bucket list of c. After generating multiple special positive sequence bucket lists, the electronic device can obtain the start suffix and end suffix of each special positive sequence bucket list. After obtaining multiple start suffixes and end suffixes, the electronic device can save the start suffixes of multiple special positive sequence bucket linked lists in the special positive sequence start array, and the electronic device can also store the end suffixes of multiple special positive sequence bucket linked lists Stored in a special positive order ending array.

In the embodiment of the present application, when the electronic device writes multiple special positive sequence suffixes into the temporary location in descending order in the first order, iteratively calculates the sequence of multiple special positive sequence suffixes through the fingerprint function to generate the first sequence. A mobile fingerprint. Moreover, when the electronic device writes the multiple special positive sequence suffixes into the temporary location in ascending order in the first sequence, iteratively calculates the sequence of multiple special positive sequence suffixes through the fingerprint function to generate the first link fingerprint. Since both the first mobile fingerprint and the first link fingerprint contain sequence information of a special positive sequence suffix. Therefore, after the construction of the suffix linked list is completed, the electronic device can determine whether the sequence of multiple special positive sequence suffixes changes during the process of constructing the suffix linked list through the first mobile fingerprint and the first link fingerprint, so as to determine the correctness of the suffix linked list. sex. Therefore, by constructing the suffix linked list through the method provided by the embodiment of the present application, the correctness verification process of the linked list can be directly integrated into the construction process of the linked list. After the construction of the suffix linked list is completed, the correctness of the suffix linked list can be directly verified without other operations. The construction method of the suffix linked list provided by the embodiment of the present application can reduce the verification time of the suffix linked list, thereby improving the construction efficiency of the suffix linked list.

S404. Inductively sort a plurality of second suffixes related to the second character type according to the first linked list, and determine a second order of the plurality of second suffixes; according to each of the second suffixes in the second order The order in and the character position of the first character of the suffix in the original character string generate a second linked list for fingerprint verification;

In the embodiment of the present application, after the first linked list is generated, the electronic device may perform inductive sorting on the plurality of second suffixes of the second character type based on the first linked list. Through the method of inductive sorting, the electronic device can determine the second sequence of multiple second suffixes. After determining the second sequence of multiple second suffixes, the electronic device can determine the special positive sequence suffix position of each second suffix in the second linked list according to the character position of the suffix first character of each second suffix in the original character string . The electronic device may also determine the pointers of the second suffixes in the second linked list according to the order of the second suffixes in the second sequence. Since the second linked list may be composed of multiple nodes, each node in the second linked list may be composed of a data field storing a suffix and a pointer field storing a pointer corresponding to the suffix. Therefore, after determining the special positive sequence suffix position of a certain second suffix, the electronic device can determine the node where the second suffix is written, and determine the pointer point of a certain second suffix by reading the content of the pointer field of the node, and then The electronic device can determine the pointer of the second suffix. Therefore, after confirming the special positive sequence suffix positions and pointers of multiple second suffixes according to the order of each second suffix in the second sequence and the character position of the first character of the suffix in the original character string, the electronic device can generate The second linked list for fingerprint verification.

In a possible implementation manner, when the electronic device is generating the second linked list, the electronic device may sort multiple second suffixes of the second character type based on the first linked list. Therefore, during the process of generating the second linked list, the electronic device can generate the second linked list according to multiple special positive sequence suffixes. Since the first fingerprint value can be obtained by the electronic device by calculating the sequence of multiple special positive sequence suffixes through the fingerprint function, the first fingerprint value can be used to describe the multiple special positive sequence suffixes used in the process of generating the second linked list first order.

In the embodiment of the present application, it should be noted that in the embodiment of the present application, the second character type may include a forward sequence type and a reverse sequence type, and the second suffix may include a forward sequence suffix and a reverse sequence suffix. Therefore, as shown in FIG. 5, S404 may also include S4041-S4044.

S4041. Determine the sequence of the reverse suffixes of the plurality of reverse suffixes according to the first linked list;

In this application, the electronic device may determine multiple reverse suffixes in the original character string and the corresponding reverse suffix positions of each reverse suffix by traversing the first linked list. After determining the multiple reverse suffixes and the corresponding reverse suffix positions of each reverse suffix through the first linked list, the electronic device can determine the sequence of the reverse suffixes of the multiple reverse suffixes through an inductive sorting method.

S4042. Generate a reversed linked list and a fingerprint of the reversed linked list according to the order of each reversed suffix in the reversed suffix sequence and the character position of the first character of the suffix in the original character string; the reversed linked list fingerprint Used to verify the reverse linked list;

In this embodiment of the application, the electronic device can determine the pointer of each reverse suffix in the reverse order linked list according to the order of each reverse suffix in the reverse order suffix sequence, and the electronic device can also determine the position of the initial character of each reverse suffix in the original string The character position determines the suffix position of each reversed suffix in the reversed linked list. According to the pointers and suffix positions corresponding to each reverse suffix, the electronic device can generate a reverse suffix linked list. During the process of generating the reverse suffix linked list, the electronic device can also calculate the fingerprint of the reverse linked list through the fingerprint function. After the reverse linked list is generated, the electronic device can verify the correctness of the reverse linked list based on the fingerprint of the reverse linked list.

In another possible implementation manner, before the electronic device generates the reverse-sequence linked list based on the first linked list, during the process of generating the first linked list, multiple special positive-sequence bucket linked lists may be generated according to the first character of the suffix. In the process of generating multiple special positive sequence bucket linked lists, the electronic device can also write the start suffix and end suffix of each special positive sequence bucket linked list into the special positive sequence start array and the special positive sequence end array respectively. The electronic device can also generate multiple reverse bucket linked lists. Wherein, the reverse-order bucket list may be a single-link list formed by linking multiple reverse-order suffixes with the same initial character of the suffix. After the electronic device generates multiple reverse bucket linked lists, it can obtain the start suffix and end suffix of each reverse bucket linked list. After obtaining multiple start suffixes and end suffixes of the reverse bucket linked list, the electronic device can save the start suffixes of multiple reverse bucket linked lists to the reverse start array, and the electronic device can also save the end suffixes of multiple reverse bucket linked lists to Reverse order ends in the array.

In the embodiment of the present application, after the electronic device determines multiple special forward-sequence bucket lists and multiple reverse-order bucket lists, it can determine multiple reverse-sequence suffixes in the order of reverse-sequence suffixes according to multiple special forward-sequence bucket lists and multiple reverse-sequence bucket lists. The sequence in and the reverse suffix positions of multiple reverse suffixes in the reverse linked list. After the electronic device determines the sequence and position of the multiple reverse suffixes, it can generate the fingerprint of the reverse linked list through a fingerprint function during the process of generating the reverse linked list. Wherein, the reverse sequence linked list fingerprint is generated by the electronic device in the process of generating the reverse sequence linked list by calculating the sequence of multiple special positive sequence suffixes through a fingerprint function.

In a possible implementation, when the electronic device generates a reverse-sequence linked list, since the special positive-sequence bucket list is a single-linked list formed by linking multiple special positive-sequence suffixes with the same initial character of the suffix, the reverse-sequence bucket list is composed of multiple A singly linked list formed by linking reverse suffixes with the same initial character of the suffix. Therefore, when generating the reverse-order linked list, the electronic device can sequentially traverse multiple special forward-order bucket linked lists and reverse-order bucket linked lists in order to determine the order and number of multiple reverse-order suffixes in the reverse-order suffix order in ascending order according to the lexicographical order of the first character of the suffix. The reverse order suffix positions of the reverse order suffixes in the reverse order linked list. For the special forward-sequence bucket list and the reverse-sequence bucket list with the same suffix first character, the electronic device can traverse the reverse-sequence bucket list first, and then traverse the special forward-sequence bucket list. For example, there are special forward-sequence bucket lists whose suffix starts with the character a, reverse-order bucket lists whose suffix starts with the character a, special forward-sequence bucket lists whose suffix starts with the character c, and reverse-order buckets whose suffix starts with the character c linked list. Therefore, the electronic device can first traverse the reverse sequence bucket list whose suffix first character is character a, then traverse the special positive sequence bucket list whose suffix first character is character a, then traverse the reverse sequence bucket list whose suffix first character is character c, and finally traverse the suffix first character The character is a special positive sequence bucket list of character c.

In the embodiment of the present application, when traversing the reverse bucket list, the electronic device can first obtain the start suffix of the reverse bucket list that needs to be traversed from the reverse start array, and obtain the reverse bucket list that needs to be traversed from the reverse end array. end suffix. According to the obtained start suffix, the electronic device can sequentially traverse each reverse suffix in the current reverse bucket linked list through the linked list pointer until the linked list pointer points to the end suffix of the current reverse bucket linked list. In the process of traversing the reverse bucket linked list, when the linked list pointer points to a certain reverse suffix in the reverse bucket linked list, the electronic device can first determine the reverse suffix position of the reverse suffix pointed to by the linked list pointer. After determining the reverse suffix position of the reverse suffix pointed to by the linked list pointer, the electronic device can determine the suffix type of the prefix and suffix corresponding to the reverse suffix pointed to by the linked list pointer through the character type array, that is, determine the first character of the prefix and suffix through the character type array character type. The electronic device can determine whether the suffix type of the prefix and suffix stored in the array is a reverse suffix type. If the suffix type of the prefix and suffix is a reverse suffix type, the electronic device can read the prefix and suffix from the original character string. After obtaining the prefix and suffix whose suffix type is the reverse suffix type, the electronic device can determine the reverse bucket linked list to which the prefix and suffix belongs according to the first character of the suffix of the prefix and suffix. Connect the obtained prefix and suffix to the end of the reverse bucket list to which the prefix and suffix belongs, and use the prefix and suffix as the end suffix of the written reverse bucket list, and update the reverse end array. Then, the electronic device can traverse the next reverse suffix of the currently traversed reverse bucket linked list according to the linked list pointer until the linked list pointer points to the end suffix of the currently traversed reverse bucket linked list.

For example, when the electronic device is traversing the reverse bucket list whose suffix starts with the character c. The electronic device can acquire the start suffix of the reverse bucket linked list whose suffix begins with the character c from the reverse start array. Then the electronic device can sequentially traverse each reverse suffix in the reverse bucket linked list whose first character is the character c through the linked list pointer until the linked list pointer points to the end suffix of the reverse bucket linked list. Assume that the reverse suffix pointed to by the linked list pointer is suf(X, pos), where X is the original string, and pos is the suffix position of the reverse suffix. The electronic device can first calculate the suffix type of the prefix and suffix of the reverse suffix suf(X, pos) according to t[pos-1], where t is an array of character types, and pos-1 is the suffix position of the prefix and suffix. When in the character type array, 0 is used to represent reverse sequence characters, and 1 is used to represent positive sequence characters, if t[pos-1]=0, that is, the suffix type of its predecessor and suffix is reverse sequence suffix type. Then the electronic device can read the preceding character X[pos-1] from the original character string X. Then the electronic device can execute Y[Lbkte[Y[pos-1]]]=pos-1 to link the prefix and suffix to the end of the suffix bucket list to which it belongs. After the link is completed, the electronic device can execute Lbkte[Y[pos-1]]=pos-1 to update the end pointer of the equal suffix bucket linked list to which the prefix and suffix belong. The electronic device may perform the above steps in a loop until the pointer of the linked list points to the end suffix of the reverse suffix bucket linked list.

In this embodiment of the application, when the electronic device traverses the special positive sequence bucket linked list, it can first obtain the start suffix of the special positive sequence bucket linked list that needs to be traversed from the special positive sequence start array, and obtain it from the special positive sequence end array. The end suffix of the special forward-ordered bucket list that needs to be traversed currently. According to the obtained start suffix, the electronic device can sequentially traverse each special positive sequence suffix in the current special positive sequence bucket linked list through the linked list pointer until the linked list pointer points to the end suffix of the currently traversed special positive sequence bucket linked list. In the process of traversing the special positive sequence bucket linked list, when the linked list pointer points to a special positive sequence suffix in the special positive sequence bucket linked list, the electronic device can first determine the special positive sequence suffix position of the special positive sequence suffix pointed to by the linked list pointer. After determining the special positive sequence suffix position of the special positive sequence suffix pointed to by the linked list pointer, the electronic device can determine the suffix type of the prefix and suffix corresponding to the special positive sequence suffix pointed to by the linked list pointer through the character type array, that is, determine through the character type array The character type of the first character following the prefix and suffix. The electronic device can determine whether the suffix type of the prefix and suffix stored in the array is a reverse suffix type. If the suffix type of the prefix and suffix is a reverse suffix type, the electronic device can read the prefix and suffix from the original character string. After obtaining the prefix and suffix whose suffix type is the reverse suffix type, the electronic device can determine the reverse bucket linked list to which the prefix and suffix belongs according to the first character of the suffix of the prefix and suffix. Connect the obtained prefix and suffix to the end of the reverse bucket list to which the prefix and suffix belongs, and use the prefix and suffix as the end suffix of the written reverse bucket list, and update the reverse end array. After updating the reverse-order end array, the electronic device can iteratively calculate the reverse-order linked list fingerprints of multiple special forward-order suffixes through the fingerprint function according to the suffix position of the special forward-order suffix pointed to by the current linked list pointer. Then, the electronic device can traverse the next special positive sequence suffix of the currently traversed special positive sequence bucket linked list according to the linked list pointer until the linked list pointer points to the end suffix of the currently traversed special positive sequence bucket linked list.

For example, when an electronic device is traversing a special positive sequence bucket list whose suffix begins with the character c. The electronic device can obtain the start suffix of the special positive sequence bucket list whose suffix begins with the character c from the special positive sequence start array. Then the electronic device can sequentially traverse each special positive sequence suffix in the special positive sequence bucket list whose first character is the character c through the linked list pointer until the linked list pointer points to the end suffix of the special positive sequence bucket linked list. Assume that the special positive sequence suffix pointed to by the linked list pointer is suf(X, pos), where X is the original string, and pos is the suffix position of the special positive sequence suffix. The electronic device can first calculate the suffix type of the prefix and suffix of the special positive sequence suffix suf(X, pos) according to t[pos-1], where t is an array of character types, and pos-1 is the suffix position of the prefix and suffix. When in the character type array, 0 is used to represent reverse sequence characters, and 1 is used to represent positive sequence characters, if t[pos-1]=0, that is, the suffix type of its predecessor and suffix is reverse sequence suffix type. Then the electronic device can read the preceding character X[pos-1] from the original character string X. Then the electronic device can execute Y[Lbkte[Y[pos-1]]]=pos-1 to link the prefix and suffix to the end of the suffix bucket list to which it belongs. After the link is completed, the electronic device can execute Lbkte[Y[pos-1]]=pos-1 to update the end pointer of the equal suffix bucket linked list to which the prefix and suffix belong. Finally, according to the suffix position pos of the special positive sequence suffix, use the fingerprint function FP iteration to calculate the reverse sequence linked list fingerprint fp2 of the ascending special positive sequence suffix. The electronic device can perform the above steps in a loop until the linked list pointer points to the end suffix of the special positive sequence suffix bucket linked list.

In the embodiment of the present application, since the electronic device iteratively calculates the suffix positions of multiple ascending special forward-order suffixes through the fingerprint function during the process of constructing the forward-order linked list, the fingerprint of the reverse-order linked list can be obtained. Since the fingerprint of the reverse linked list is calculated by the corresponding suffix positions of multiple special positive sequence suffixes in the process of constructing the reverse linked list, the fingerprint of the reverse linked list can include multiple special positive sequence suffixes in the process of constructing the reverse linked list. Suffix information in ascending order. Therefore, the electronic device can directly determine whether the reverse sequence linked list is correct by judging whether the fingerprint of the forward sequence linked list is equal to the first link fingerprint. Therefore, by constructing the suffix linked list through the method provided by the embodiment of the present application, the correctness of the constructed reversed linked list can be confirmed during the process of constructing the suffix linked list, without decompressing the reversed linked list. Therefore, the method provided by the embodiment of the present application can save the verification time and verification space of the suffix linked list. In addition, because the embodiment of the present application integrates the correctness verification method of the reverse linked list into the process of constructing the linked list, the electronic device can give the verification result of the reversed linked list based on the first mobile fingerprint and the fingerprint of the reversed linked list when the construction of the reversed linked list is completed, and can Improve the verification efficiency of the suffix linked list.

S4043. Determine the sequence of the positive sequence suffixes of the plurality of positive sequence suffixes according to the reverse sequence linked list;

In the embodiment of the present application, the electronic device can determine the position of the reverse sequence suffix corresponding to the multiple normal sequence suffixes in the original character string by traversing the reverse sequence linked list. After determining the multiple positive-sequence suffixes and the corresponding positive-sequence suffix positions through the first linked list, the electronic device can determine the order of the multiple positive-sequence suffixes through an inductive sorting method.

S4044. Generate a positive sequence linked list and a fingerprint of the positive sequence linked list according to the order of each positive sequence suffix in the positive sequence suffix sequence and the character position of the first character of the suffix in the original character string; The positive sequence linked list fingerprint is used to verify the positive sequence linked list.

In this embodiment of the application, the electronic device can determine the pointers of each positive-sequence suffix in the positive-sequence linked list according to the order of each positive-sequence suffix in the sequence of the positive-sequence suffix. The character position in the original string determines the suffix position of each positive-sequence suffix in the positive-sequence linked list. According to the pointers and suffix positions corresponding to each positive sequence suffix, the electronic device can generate a positive sequence suffix linked list. In the process of generating the positive sequence suffix linked list, the electronic device can also calculate the fingerprint of the positive sequence linked list through the fingerprint function. After the positive sequence linked list is generated, the electronic device can verify the correctness of the positive sequence linked list based on the positive sequence linked list fingerprint.

In another possible implementation manner, before the electronic device generates the forward-sequence linked list based on the reverse-sequence linked list, before the process of generating the reverse-sequence linked list, it may generate multiple reverse-sequence bucket linked lists according to the first character of the suffix. During the process of generating multiple reverse bucket linked lists, the electronic device may also write the start suffix and end suffix of each reverse bucket linked list into the reverse start array and the reverse end array respectively. In addition, the electronic device can also generate multiple positive sequence bucket linked lists. Wherein, the positive sequence bucket linked list may be a single linked list formed by linking multiple positive sequence suffixes with the same initial character of the suffix. After the electronic device generates multiple positive sequence bucket lists, it can obtain the start suffix and end suffix of each positive sequence bucket list. After obtaining multiple start suffixes and end suffixes of the positive sequence bucket list, the electronic device can save the start suffixes of the multiple positive sequence bucket list in the positive sequence start array, and the electronic device can also save the multiple positive sequence bucket list The end suffix is stored in the end array in positive order.

In the embodiment of the present application, after the electronic device determines the multiple forward-sequence bucket lists and the multiple reverse-order bucket lists, it can determine the order of the forward-sequence suffixes in the forward-sequence suffixes according to the multiple forward-sequence bucket lists and the multiple reverse-sequence bucket lists. The order in and the positive-order suffix positions of multiple positive-order suffixes in the positive-order linked list. After the electronic device determines the order of the multiple forward-sequence suffixes and the positions of the reverse-order suffixes, it can generate the fingerprint of the forward-sequence linked list through a fingerprint function during the process of generating the forward-sequence linked list. Wherein, the positive sequence linked list fingerprint is generated by the electronic device in the process of generating the positive sequence linked list by calculating the sequence of multiple special positive sequence suffixes through a fingerprint function.

In a possible implementation manner, when the electronic device generates the positive sequence linked list, the positive sequence bucket linked list is a single linked list formed by linking multiple positive sequence suffixes with the same initial character of the suffix. The reverse bucket linked list is a singly linked list formed by linking multiple reverse suffixes with the same initial character of the suffix. Therefore, when generating a forward-sequence linked list, the electronic device can sequentially traverse multiple forward-sequence bucket linked lists and reverse-sequence bucket linked lists in ascending order according to the lexicographical order of the first character of the suffix to determine the order of multiple forward-sequence suffixes in the positive-sequence suffix order and the positive-order suffix positions of multiple positive-order suffixes in the positive-order linked list. For the forward-sequence bucket list and the reverse-sequence bucket list with the same suffix first character, the electronic device can traverse the forward-sequence bucket list first, and then traverse the reverse-sequence bucket list. For example, there are existing positive-sequence bucket lists whose suffix starts with the character a, reverse-order bucket lists whose suffix starts with the character a, forward-order bucket lists whose suffix starts with the character c, and reverse-order bucket lists whose suffix starts with the character c. Therefore, the electronic device can first traverse the positive sequence bucket list whose suffix first character is the character a, then traverse the reverse sequence bucket list whose suffix first character is the character a, then traverse the positive sequence bucket list whose suffix first character is the character c, and finally traverse the suffix first The character is a reverse bucket list of character c.

In the embodiment of the present application, when traversing the positive sequence bucket list, the electronic device can first obtain the start suffix of the positive sequence bucket list that needs to be traversed from the positive sequence start array, and obtain the current sequence bucket list to be traversed from the positive sequence end array. The end suffix of the positive order bucket list. According to the obtained start suffix, the electronic device can sequentially traverse each positive sequence suffix in the current positive sequence bucket linked list through the linked list pointer until the linked list pointer points to the end suffix of the currently traversed positive sequence bucket linked list. In the process of traversing the positive sequence bucket linked list, when the linked list pointer points to a certain positive sequence suffix in the positive sequence bucket linked list, the electronic device can first determine the positive sequence suffix position of the positive sequence suffix pointed to by the linked list pointer. After determining the positive sequence suffix position of the positive sequence suffix pointed to by the linked list pointer, the electronic device can determine the suffix type of the prefix and suffix corresponding to the positive sequence suffix pointed to by the linked list pointer through the character type array, that is, determine the prefix and suffix through the character type array The character type of the first character of . The electronic device can determine whether the suffix type of the prefix and suffix stored in the array is a positive sequence suffix type. If the suffix type of the prefix and suffix is a positive sequence suffix type, the electronic device can read the prefix and suffix from the original character string. After obtaining the prefix and suffix whose suffix type is the positive sequence suffix type, the electronic device can determine the reverse-order bucket list to which the prefix and suffix belongs according to the first character of the suffix of the prefix and suffix. Connect the obtained prefix and suffix to the end of the reverse-order bucket list to which the prefix and suffix belongs, and use the prefix and suffix as the end suffix of the written positive-order bucket list to update the positive-order end array. After updating the positive sequence end array, the electronic device can determine whether the positive sequence suffix pointed to by the current linked list pointer and/or the preceding and suffix corresponding to the positive sequence suffix are special positive sequence suffixes according to the character type array. If the positive sequence suffix pointed to by the current linked list pointer and/or the corresponding prefix and suffix of the positive sequence suffix is a special positive sequence suffix, the electronic device can iteratively calculate multiple special positive sequence suffixes through the fingerprint function according to the suffix position corresponding to the special positive sequence suffix. Ordinal linked list fingerprint of sequence suffix. The electronic device can traverse the next positive sequence suffix of the currently traversed positive sequence bucket linked list according to the linked list pointer until the linked list pointer points to the end suffix of the currently traversed positive sequence bucket linked list.

For example, when the electronic device is traversing the positive sequence bucket list whose suffix starts with the character c. The electronic device can obtain the start suffix of the positive sequence bucket list whose suffix starts with the character c from the positive sequence start array. Then the electronic device can sequentially traverse each positive sequence suffix in the positive sequence bucket linked list whose first character is the character c through the linked list pointer until the linked list pointer points to the end suffix of the positive sequence bucket linked list. Assume that the positive sequence suffix pointed to by the linked list pointer is suf(X, pos), where X is the original string, and pos is the suffix position of the positive sequence suffix. The electronic device can first calculate the suffix type of the prefix and suffix of the positive sequence suffix suf(X, pos) according to t[pos-1], where t is an array of character types, and pos-1 is the suffix position of the prefix and suffix. When in the character type array, 0 is used to represent reverse sequence characters, and 1 is used to represent positive sequence characters, if t[pos-1]=1, that is, the suffix type of its predecessor and suffix is positive sequence suffix type. Then the electronic device can read the preceding character X[pos-1] from the original character string X. Then the electronic device can execute Y[Sbkte[Y[pos-1]]]=pos-1, and link the prefix and suffix to the end of the suffix bucket list to which it belongs. After the link is completed, the electronic device can execute Sbkte[Y[pos-1]]=pos-1 to update the end pointer of the equal suffix bucket linked list to which the prefix and suffix belong. Finally, based on the corresponding suffix position pos of the positive sequence suffix currently pointed to by the linked list pointer and the corresponding suffix position pos-1 of the prefix and suffix of the positive sequence suffix, the electronic device can determine the positive sequence suffix currently pointed to by the linked list pointer and / through the character type array Or whether the preceding suffix of the positive sequence suffix is a special positive sequence suffix. If the positive sequence suffix currently pointed to by the linked list pointer and/or the prefix and suffix of the positive sequence suffix is a special positive sequence suffix, the electronic device can use the fingerprint function FP to iterate and calculate the positive sequence linked list fingerprint fp3 of multiple descending special positive sequence suffixes . The electronic device can perform the above steps in a loop until the linked list pointer points to the end suffix of the positive sequence suffix bucket linked list.

In the embodiment of the present application, when traversing the reverse bucket list, the electronic device can first obtain the start suffix of the reverse bucket list that needs to be traversed from the reverse start array, and obtain the reverse bucket list that needs to be traversed from the reverse end array. end suffix. According to the obtained start suffix, the electronic device can sequentially traverse each reverse suffix in the current reverse bucket linked list through the linked list pointer until the linked list pointer points to the end suffix of the current reverse bucket linked list. In the process of traversing the reverse bucket linked list, when the linked list pointer points to a certain reverse suffix in the reverse bucket linked list, the electronic device can first determine the reverse suffix position of the reverse suffix pointed to by the linked list pointer. After determining the reverse suffix position of the reverse suffix pointed to by the linked list pointer, the electronic device can determine the suffix type of the prefix and suffix corresponding to the reverse suffix pointed to by the linked list pointer through the character type array, that is, determine the first character of the prefix and suffix through the character type array character type. The electronic device can determine whether the suffix type of the prefix and suffix stored in the array is a positive sequence suffix type. If the suffix type of the prefix and suffix is a positive sequence suffix type, the electronic device can read the prefix and suffix from the original character string. After obtaining the prefix and suffix whose suffix type is the positive sequence suffix type, the electronic device can determine the positive sequence bucket list to which the prefix and suffix belongs according to the first character of the suffix of the prefix and suffix. Connect the obtained prefix and suffix to the end of the positive sequence bucket list to which the prefix and suffix belongs, and use the prefix and suffix as the end suffix of the written positive sequence bucket list to update the positive sequence end array. Then, the electronic device can traverse the next reverse suffix of the currently traversed reverse bucket linked list according to the linked list pointer until the linked list pointer points to the end suffix of the currently traversed reverse bucket linked list.

For example, when the electronic device is traversing the reverse bucket list whose suffix starts with the character c. The electronic device can acquire the start suffix of the reverse bucket linked list whose suffix begins with the character c from the reverse start array. Then the electronic device can sequentially traverse each reverse suffix in the reverse bucket linked list whose first character is the character c through the linked list pointer until the linked list pointer points to the end suffix of the reverse bucket linked list. Assume that the reverse suffix pointed to by the linked list pointer is suf(X, pos), where X is the original string, and pos is the suffix position of the reverse suffix. The electronic device can first calculate the suffix type of the prefix and suffix of the reverse suffix suf(X, pos) according to t[pos-1], where t is an array of character types, and pos-1 is the suffix position of the prefix and suffix. When in the character type array, 0 is used to represent reverse sequence characters, and 1 is used to represent positive sequence characters, if t[pos-1]=1, that is, the suffix type of its predecessor and suffix is positive sequence suffix type. Then the electronic device can read the preceding character X[pos-1] from the original character string X. Then the electronic device can execute Y[Sbkte[Y[pos-1]]]=pos-1, and link the prefix and suffix to the end of the suffix bucket list to which it belongs. After the link is completed, the electronic device can execute Sbkte[Y[pos-1]]=pos-1 to update the end pointer of the equal suffix bucket linked list to which the prefix and suffix belong. The electronic device may perform the above steps in a loop until the pointer of the linked list points to the end suffix of the reverse suffix bucket linked list.

In the embodiment of the present application, since the electronic device iteratively calculates the suffix positions of multiple descending special positive sequence suffixes through the fingerprint function in the process of constructing the positive sequence linked list, the fingerprint of the positive sequence linked list can be obtained. In the process of constructing the positive sequence linked list, it is calculated by the corresponding suffix positions of multiple special positive sequence suffixes, so the positive sequence linked list fingerprint can contain the descending sequence information of multiple special positive sequence suffixes in the process of constructing the positive sequence linked list . Therefore, the electronic device can directly determine whether the positive sequence linked list is correct by judging whether the positive sequence linked list fingerprint is equal to the first link fingerprint. Therefore, by constructing the suffix linked list through the method provided in the embodiment of the present application, the correctness of the constructed positive sequence linked list can be determined during the process of constructing the suffix linked list. Therefore, the method provided by the embodiment of the present application can save time and space for verifying the suffix linked list. In addition, because in the embodiment of the present application, the electronic device determines the fingerprint of the positive sequence linked list and the first link fingerprint through iterative calculation of the fingerprint function, the accuracy of verifying the suffix linked list through the method provided in the embodiment of the present application is relatively high.

S405. Generate a suffix linked list corresponding to the original character string according to the second linked list of each of the second character types.

In the embodiment of the present application, after the electronic device generates a plurality of second linked lists of the second character type, the suffix corresponding to the original character string can be generated by linking the plurality of second suffixes in the plurality of second linked lists. linked list.

In a possible implementation manner, after the electronic device generates the reverse-order linked list and the forward-order linked list, it can determine the start suffix and the end suffix of multiple reverse-order bucket linked lists through the reverse-order start array and the reverse-order end array. The electronic device can also determine the start suffix and end suffix of multiple positive sequence bucket linked lists through the positive sequence start array and the positive sequence end array. Based on the start suffix and end suffix of multiple reverse-sequence bucket linked lists and the start suffix and end suffix of multiple positive-sequence bucket linked lists, the electronic device can link multiple forward-order suffixes and reverse-order suffixes by traversing the forward-order linked list and reverse-order linked list Get up and generate the suffix linked list corresponding to the original string. The forward-order linked list and the reverse-order linked list may be a descending forward-order linked list and a descending reverse-order linked list, and the corresponding generated suffix linked list may also be a descending-order suffix linked list.

In the embodiment of the present application, after the electronic device generates the suffix linked list, it can verify the correctness of the suffix linked list according to the first fingerprint and the second fingerprint. In a possible implementation manner, the first fingerprint may include a first mobile fingerprint and a first link fingerprint, and the second fingerprint may include a reverse-sequence linked list fingerprint and a forward-sequence linked list fingerprint. The first mobile fingerprint contains descending sequence information of multiple special positive sequence suffixes, and the first link fingerprint contains ascending sequence information of multiple special positive sequence suffixes. The reverse linked list fingerprint contains the descending order information of multiple special positive sequence suffixes used in the process of constructing the reverse linked list. The positive sequence linked list fingerprint contains the ascending order information of multiple special positive sequence suffixes used in the process of constructing the positive sequence linked list.

Therefore, the electronic device can determine whether the descending order of multiple special forward-order suffixes changes during the process of constructing the reverse-order linked list by judging whether the first mobile fingerprint is equal to the reverse-order linked list fingerprint. If the first mobile fingerprint is equal to the fingerprint of the reverse linked list, the electronic device can judge that the descending order of the multiple special positive sequence suffixes has not changed during the process of constructing the reverse linked list, that is, the electronic device can judge that the reverse linked list is correct. All reverse suffixes are not missing, and the suffix positions of each reverse suffix are correct. If the first mobile fingerprint is not equal to the fingerprint of the reverse linked list, the electronic device can judge that the descending order of multiple special positive sequence suffixes has changed during the process of constructing the reverse linked list, that is, the electronic device can judge that there may be The case where the legacy reverse suffix or the suffix position of the reverse suffix corresponds to an error has been fixed.

The electronic device can determine whether the ascending order of multiple special forward-sequence suffixes changes during the process of constructing the forward-sequence linked list by judging whether the first link fingerprint is equal to the forward-sequence linked list fingerprint. If the first link fingerprint is equal to the fingerprint of the positive-sequence linked list, the electronic device can judge that the ascending order of multiple special positive-sequence suffixes has not changed during the process of constructing the positive-sequence linked list, that is, the electronic device can judge that the positive-sequence linked list is correct. Each positive sequence suffix in the sequence linked list is not missing, and the suffix position of each positive sequence suffix is correct. If the first link fingerprint is not equal to the fingerprint of the positive sequence linked list, then the electronic device can judge that the ascending order of multiple special positive sequence suffixes has changed during the process of constructing the positive sequence linked list, that is, the electronic device can judge that in the process of constructing the positive sequence linked list There may be cases where the legacy positive sequence suffix or the suffix position of the positive sequence suffix corresponds incorrectly.

In the embodiment of the present application, for the original character string X of any length, the electronic device first uses the inductive sorting method to sort the special positive sequence suffixes in situ, and saves the sorted multiple special positive sequence suffixes in a temporary location. During saving, the electronic device may use the fingerprint function FP to iteratively calculate the first mobile fingerprint of the special positive sequence suffix in descending order. Then the electronic device can link the special positive sequence suffixes to the suffix positions corresponding to the corresponding special positive sequence suffixes in ascending order. During linking, the electronic device can use the fingerprint function FP to iteratively calculate the first link fingerprint of the ascending special positive sequence suffix. Next, in the process of inductively sorting the reverse-order suffix and forward-order suffix linked lists, the electronic device can use the fingerprint function FP to iteratively calculate the fingerprints of the reverse-order linked list and the forward-order linked list. Finally, the electronic device can verify the correctness of the entire suffix linked list by judging whether the first mobile fingerprint is equal to the fingerprint of the reverse-sequence linked list, and whether the first link fingerprint is equal to the fingerprint of the forward-sequence linked list. If the first mobile fingerprint is equal to the fingerprint of the reverse-sequence linked list and the first link fingerprint is equal to the fingerprint of the forward-sequence linked list, the electronic device can determine that the suffix linked list stores the correct suffix order. If the first mobile fingerprint is not equal to the fingerprint of the reverse-sequence linked list and/or the first link fingerprint is not equal to the fingerprint of the forward-sequence linked list, otherwise the electronic device may determine that the sequence of suffixes stored in the suffix linked list is incorrect. The principle is that the order of special forward suffixes determines the order of reverse suffixes, and the order of reverse suffixes determines the order of forward suffixes. And because the special positive sequence suffix is a special case of the positive sequence suffix. Therefore, if the sorting and linking results are correct, multiple special positive-order suffixes before sorting L-type suffixes have the same fingerprint as multiple special positive-order suffixes after sorting S-type suffixes, that is, the special positive-order suffixes retain the same suffix sequence information.

In the construction method of the suffix linked list proposed in the embodiment of the present application, due to the process of verifying the correctness of the constructed suffix linked list, only the first fingerprint value and the second fingerprint value need to be compared, and no other operations are required on the constructed suffix linked list , and no need to operate on raw strings. Therefore, the suffix linked list construction method provided by the embodiment of the present application is used to construct the suffix linked list. When verifying the correctness of the constructed suffix linked list, the space overhead for verifying the correctness of the linked list is negligible, and the time overhead is relative to the time overhead of constructing the linked list. Also very small. In addition, the construction method of the suffix linked list integrated with correctness verification provided by the embodiment of the present application avoids verifying the correctness of the suffix linked list by directly comparing the suffix dictionary order, and realizes the verification of the correctness of the linked list during the construction of the suffix linked list. In practical application situations, using the method proposed in the embodiment of this application, not only can the construction of the suffix linked list be realized, but also the correctness of the construction result can be verified, and the time and space overhead of the verification method is very small.

It should be noted that the sequence numbers of the steps in the above embodiments do not mean the order of execution, the execution order of each process should be determined by its functions and internal logic, and should not constitute any limited.

Referring to FIG. 6 , it shows a schematic diagram of a linked list generation device with its own verification function provided by the embodiment of the present application, which may specifically include a special positive sequence suffix determination module 601, a first sequence determination module 602, and a first linked list generation module 603 , the second linked list generating module 604 and the suffix linked list generating module 605, wherein:

The special positive sequence suffix determination module 601 is used to generate a plurality of special positive sequence suffixes about the original character string according to the character type array; the character type array is generated according to the character type corresponding to each character in the original character string; The special positive sequence suffix is the character type of the first character of the suffix is the suffix of the special positive sequence type; the character type of each character is determined by the character size between each character and its adjacent characters;

The first order determination module 602 is configured to perform inductive sorting on the plurality of special positive sequence suffixes, and determine the first order of the plurality of special positive sequence suffixes;

The first linked list generation module 603 is used to generate the first sequence for fingerprint verification according to the order of each of the special positive sequence suffixes in the first sequence and the character position of the first character of the suffix in the original string. a linked list;

The second linked list generation module 604 is configured to perform inductive sorting on a plurality of second suffixes related to the second character type according to the first linked list, and determine the second order of the plurality of second suffixes; according to each of the second suffixes The order of the suffix in the second order and the character position of the first character of the suffix in the original character string generate a second linked list for fingerprint verification;

A suffix linked list generating module 605, configured to generate a suffix linked list corresponding to the original character string according to the second linked list of each of the second character types.

Wherein, the first linked list generating module 603 can also be used to generate a first fingerprint according to a plurality of said special positive sequence suffixes; said first fingerprint is used to describe a plurality of said special positive sequence suffixes when generating said first linked list the first order of

The second linked list generation module 604 can also be used to generate a second fingerprint according to a plurality of said special positive sequence suffixes; said second fingerprint is used to describe the first of multiple said special positive sequence suffixes when generating said second linked list a sequence;

The suffix linked list generating module 605 may also be configured to verify the suffix linked list according to the first fingerprint and the second fingerprint.

The second linked list generating module 604 can also be used to determine the reverse suffix sequence of multiple reverse suffixes according to the first linked list; according to the order of each reverse suffix in the reverse suffix sequence and the suffix The character position of the first character in the original character string generates a reversed linked list and the fingerprint of the reversed linked list; the fingerprint of the reversed linked list is used to verify the reversed linked list; according to the reversed linked list, determine a plurality of positive The positive sequence suffix sequence of the sequential suffix; according to the order of each positive sequence suffix in the positive sequence suffix sequence and the character position of the first character of the suffix in the original character string, the positive sequence linked list and the A positive sequence linked list fingerprint; the positive sequence linked list fingerprint is used to verify the positive sequence linked list.

The first linked list generation module 603 can also be used to determine the character position of the first character of the suffix of each of the special positive sequence suffixes in the original character string according to the character type array; In the descending order in the above-mentioned first order, write the plurality of special positive sequence suffixes in the temporary positions corresponding to each of the special positive sequence suffixes in turn to generate a temporary linked list; the temporary positions are the initial characters of each of the suffixes The adjacent position of the corresponding character position in the original character string; according to the fingerprint function, the temporary positions of a plurality of the special positive sequence suffixes are calculated to generate the first mobile fingerprint; according to the special positive sequence suffix in the first Ascending order in the order, sequentially write the plurality of special positive sequence suffixes into the corresponding character positions of each of the special positive sequence suffixes to generate a first linked list; The position is calculated to generate the first link fingerprint.

The suffix linked list generating module 605 can also be used to verify the suffix linked list according to the first mobile fingerprint, the first link fingerprint, the reverse sequence linked list fingerprint and the forward sequence linked list fingerprint; if the first If the moving fingerprint is equal to the fingerprint of the reverse-sequence linked list and the fingerprint of the first link is equal to the fingerprint of the forward-sequence linked list, then the verification of the suffix linked list passes.

The second linked list generation module 604 can also be used to generate a plurality of special forward-order bucket linked lists and a plurality of reverse-order bucket linked lists about the first linked list according to the first character of the suffix; the reverse-order bucket linked list includes a plurality of the reverse-order suffixes ; The special forward-sequence bucket list includes a plurality of the special forward-sequence suffixes; according to the plurality of the special forward-sequence bucket list and the plurality of reverse-sequence bucket lists, determine the order of the reverse-sequence suffixes in the reverse-sequence suffix , and generate reverse-order linked list fingerprints about multiple special positive-order suffixes through the fingerprint function.

The second linked list generation module 604 can also be used to generate multiple reversed bucket linked lists and multiple forward linked list buckets of the reversed linked list according to the first character of the suffix; the reversed bucket linked list includes multiple reversed suffixes; The positive sequence bucket linked list includes a plurality of the positive sequence suffixes; according to the multiple positive sequence bucket linked lists and the multiple reverse sequence bucket linked lists, the order of the multiple positive sequence suffixes in the positive sequence suffix sequence is determined , and generate positive sequence linked list fingerprints about a plurality of special positive sequence suffixes through the fingerprint function.

As for the device embodiment, since it is basically similar to the method embodiment, the description is relatively simple, and for related details, please refer to the description of the method embodiment.

Referring to FIG. 7 , it shows a schematic diagram of a terminal device provided by an embodiment of the present application. As shown in FIG. 7 , a terminal device 700 in this embodiment of the present application includes: a processor 710 , a memory 720 , and a computer program 721 stored in the memory 720 and operable on the processor 710 . When the processor 710 executes the computer program 721, it implements the steps in each embodiment of the method for generating a linked list with a verification function, such as steps S401 to S405 shown in FIG. 4 . Alternatively, when the processor 710 executes the computer program 721, functions of the modules/units in the above-mentioned device embodiments, for example, the functions of the modules 601 to 605 shown in FIG. 6 , are implemented.

Exemplarily, the computer program 721 can be divided into one or more modules/units, and the one or more modules/units are stored in the memory 720 and executed by the processor 710 to complete this application. The one or more modules/units may be a series of computer program instruction segments capable of accomplishing specific functions, and the instruction segments may be used to describe the execution process of the computer program 721 in the terminal device 700 . For example, the computer program 721 can be divided into a special positive sequence suffix determination module, a first order determination module, a first linked list generation module, a second linked list generation module and a suffix linked list generation module, and the specific functions of each module are as follows:

The special positive sequence suffix determination module is used to generate a plurality of special positive sequence suffixes about the original character string according to the character type array; the character type array is generated according to the character type corresponding to each character in the original character string; the The first suffix is that the character type of the first character of the suffix is a suffix of a special positive sequence type; the character type of each character is determined by the character size between each character and its adjacent characters;

A first order determination module, configured to inductively sort the plurality of special positive sequence suffixes, and determine the first order of the plurality of special positive sequence suffixes;

The first linked list generation module is used to generate the first list for fingerprint verification according to the order of each of the special positive sequence suffixes in the first order and the character position of the first character of the suffix in the original string. linked list;

The second linked list generation module is used to inductively sort a plurality of second suffixes related to the second character type according to the first linked list, and determine the second order of the plurality of second suffixes; according to each of the second suffixes In the order in the second order and the character position of the first character of the suffix in the original character string, generate a second linked list for fingerprint verification;

A suffix linked list generating module, configured to generate a suffix linked list corresponding to the original character string according to the second linked list of each of the second character types.

The terminal device 700 may be the electronic device in the foregoing embodiments, and the electronic device may be a computing device such as a desktop computer or a cloud server. The terminal device 700 may include, but not limited to, a processor 710 and a memory 720 . Those skilled in the art can understand that FIG. 7 is only an example of a terminal device 700, and does not constitute a limitation to the terminal device 700. It may include more or less components than those shown in the figure, or combine certain components, or be different. components, for example, the terminal device 700 may also include input and output devices, network access devices, buses, and so on.

The processor 710 can be a central processing unit (Central Processing Unit, CPU), and can also be other general-purpose processors, digital signal processors (Digital Signal Processor, DSP), application specific integrated circuits (Application Specific Integrated Circuit, ASIC), off-the-shelf Programmable gate array (Field-Programmable Gate Array, FPGA) or other programmable logic devices, discrete gate or transistor logic devices, discrete hardware components, etc. A general-purpose processor may be a microprocessor, or the processor may be any conventional processor, or the like.

The storage 720 may be an internal storage unit of the terminal device 700 , such as a hard disk or memory of the terminal device 700 . The memory 720 may also be an external storage device of the terminal device 700, such as a plug-in hard disk equipped on the terminal device 700, a smart memory card (Smart Media Card, SMC), a secure digital (Secure Digital, SD) card , Flash Card (Flash Card) and so on. Further, the memory 720 may also include both an internal storage unit of the terminal device 700 and an external storage device. The memory 720 is used to store the computer program 721 and other programs and data required by the terminal device 700 . The memory 720 can also be used to temporarily store data that has been output or will be output.

The embodiment of the present application also discloses a terminal device, including a memory, a processor, and a computer program stored in the memory and operable on the processor. When the processor executes the computer program, the aforementioned The method for generating a linked list with a verification function described in each embodiment.

The embodiment of the present application also discloses a computer-readable storage medium, the computer-readable storage medium stores a computer program, and when the computer program is executed by a processor, it realizes the self-contained verification function as described in the foregoing embodiments Linked list generation method.

The embodiment of the present application also discloses a computer program product. When the computer program product is run on a computer, the computer is made to execute the method for generating a linked list with a verification function described in the foregoing embodiments.

The above-mentioned embodiments are only used to illustrate the technical solution of the present application, but not to limit it. Although the present application has been described in detail with reference to the aforementioned embodiments, those skilled in the art should understand that: they can still modify the technical solutions described in the aforementioned embodiments, or perform equivalent replacements for some of the technical features; and these Any modification or replacement that does not make the essence of the corresponding technical solutions deviate from the spirit and scope of the technical solutions of the embodiments of the present application shall be included within the protection scope of the present application.

Claims (7)

1. A method for generating a linked list with a verification function, characterized in that, comprising: Generate a plurality of special positive sequence suffixes about the original string according to the character type array; the character type array is generated according to the character type corresponding to each character in the original string; the special positive sequence suffix is the first character of the suffix The character type is the suffix of the special positive sequence type; the character type of each character is determined by the character size between each character and its adjacent characters; the special positive sequence type is used to indicate that the previous character is a reverse sequence character The character type corresponding to the ordinal character or the character type corresponding to the end character of the original character string; performing inductive sorting on the multiple special positive sequence suffixes, and determining the first order of the multiple special positive sequence suffixes; According to the order of each of the special positive sequence suffixes in the first order and the character position of the first character of the suffix in the original character string, a first linked list for fingerprint verification is generated, and according to the multiple The special positive sequence suffix generates a first fingerprint; the first fingerprint is used to describe the first sequence of multiple special positive sequence suffixes when generating the first linked list; According to the first linked list, a plurality of second suffixes related to the second character type are inductively sorted to determine a second order of the plurality of second suffixes; according to the order of each of the second suffixes in the second order and The first character of the suffix is in the character position of the original character string, generating a second linked list for fingerprint verification, and generating a second fingerprint according to a plurality of the special positive sequence suffixes; the second fingerprint is used for Describe the first sequence of multiple special positive sequence suffixes when generating the second linked list; generating a suffix linked list corresponding to the original character string according to the second linked list of each of the second character types, and verifying the suffix linked list according to the first fingerprint and the second fingerprint; Wherein, the first fingerprint includes a first mobile fingerprint and a first link fingerprint, and according to the order of each of the special positive sequence suffixes in the first sequence and the first character of the suffix in the original character string character position, generate the first linked list for fingerprint verification, and generate the first fingerprint according to a plurality of said special positive sequence suffixes, including: According to the character type array, determine the character position of the suffix first character of each of the special positive sequence suffixes in the original character string; According to the descending order of the special positive sequence suffixes in the first order, sequentially write the plurality of special positive sequence suffixes into the temporary positions corresponding to each of the special positive sequence suffixes to generate a temporary linked list; the temporary The position is the adjacent position of the corresponding character position of the first character of each suffix in the original character string; Calculating the temporary positions of a plurality of said special positive sequence suffixes according to a fingerprint function to generate a first mobile fingerprint; According to the ascending order of the special positive sequence suffixes in the first order, sequentially write the multiple special positive sequence suffixes into the corresponding character positions of each of the special positive sequence suffixes to generate a first linked list; Calculating character positions of a plurality of said special positive sequence suffixes according to a fingerprint function to generate a first link fingerprint; Wherein, the second character type includes a reverse sequence character and a positive sequence character, the corresponding second suffix includes a reverse sequence suffix and a positive sequence suffix, the second linked list includes a reverse sequence linked list and a positive sequence linked list, and the second sequence includes a reverse sequence suffix order and positive sequence suffix sequence, the second fingerprint includes positive sequence linked list fingerprints and reverse sequence linked list fingerprints, the plurality of second suffixes related to the second character type are sorted inductively according to the first linked list, and the plurality of second suffixes of the second character type are determined. The second order of the two suffixes; according to the order of each of the second suffixes in the second order and the character position of the first character of the suffix in the original character string, generate a second order for fingerprint verification Linked list, and generate the second fingerprint according to a plurality of said special positive sequence suffixes, including: determining the sequence of the reverse suffixes of the plurality of reverse suffixes according to the first linked list; According to the order of each of the reverse suffixes in the reverse suffix sequence and the character position of the first character of the suffix in the original character string, a reverse linked list and a fingerprint of the reverse linked list are generated; the fingerprint of the reverse linked list is used for Verifying the reverse linked list; determining the sequence of the positive sequence suffixes of the plurality of positive sequence suffixes according to the reverse sequence linked list; According to the order of each of the positive sequence suffixes in the positive sequence suffix sequence and the character position of the first character of the suffix in the original character string, a positive sequence linked list and a fingerprint of the positive sequence linked list are generated; The sequence linked list fingerprint is used to verify the positive sequence linked list. 2. The method according to claim 1, wherein said verifying said suffix linked list according to said first fingerprint and said second fingerprint comprises: Verifying the suffix linked list according to the first mobile fingerprint, the first link fingerprint, the reverse linked list fingerprint and the forward linked list fingerprint; If the first mobile fingerprint is equal to the fingerprint of the reverse-sequence linked list and the first link fingerprint is equal to the fingerprint of the forward-sequence linked list, then the verification of the suffix linked list passes. 3. The method according to claim 1 or claim 2, wherein the reverse order suffix order of a plurality of said reverse order suffixes is determined according to said first linked list; according to each said reverse order suffix in said reverse order suffix The order in the order and the character position of the first character of the suffix in the original character string generate a reversed linked list and a reversed linked list fingerprint, including: According to the first character of the suffix, a plurality of special forward-order bucket linked lists and a plurality of reverse-order bucket linked lists about the first linked list are generated; the reverse-order bucket linked list includes a plurality of reverse-order suffixes; the special forward-order bucket linked list includes multiple one of said special positive sequence suffixes; Determine the order of multiple reverse suffixes in the reverse suffix order according to the multiple special forward-order bucket lists and multiple reverse-order bucket lists, and generate information about the multiple special forward-order suffixes through a fingerprint function Reverse linked list fingerprint. 4. The method according to claim 1 or claim 2, wherein the positive sequence suffix includes the special positive sequence suffix, and the positive sequence of a plurality of the positive sequence suffixes is determined according to the reverse sequence linked list. Suffix order; according to the order of each of the positive sequence suffixes in the positive sequence suffix sequence and the character position of the first character of the suffix in the original character string, a positive sequence linked list and a positive sequence linked list fingerprint are generated, including: According to the first character of the suffix, generate a plurality of reverse-order bucket linked lists and a plurality of forward-order bucket linked lists about the reverse-order linked list; the reverse-order bucket linked list includes a plurality of the reverse-order suffixes; positive sequence suffix; Determine the order of the plurality of forward-order suffixes in the order of the forward-order suffixes according to the plurality of the forward-order bucket lists and the plurality of the reverse-order bucket lists, and generate information about the plurality of special forward-order suffixes through a fingerprint function The positive sequence linked list fingerprint. 5. A linked list generation device with self-contained verification function, characterized in that, comprising: The special positive sequence suffix determination module is used to generate a plurality of special positive sequence suffixes about the original character string according to the character type array; the character type array is generated according to the character type corresponding to each character in the original character string; the The special positive sequence suffix is the character type of the first character of the suffix is the suffix of the special positive sequence type; the character type of each character is determined by the character size between each character and its adjacent characters; the special positive sequence type is used for Indicates that the previous character is a character type corresponding to a character in a reverse sequence or a character type corresponding to an end character of the original character string; A first order determination module, configured to inductively sort the plurality of special positive sequence suffixes, and determine the first order of the plurality of special positive sequence suffixes; The first linked list generation module is used to generate the first list for fingerprint verification according to the order of each of the special positive sequence suffixes in the first order and the character position of the first character of the suffix in the original string. A linked list, and is used to generate a first fingerprint according to a plurality of the special positive sequence suffixes; the first fingerprint is used to describe the first order of the multiple special positive sequence suffixes when generating the first linked list; Wherein, the first fingerprint includes a first mobile fingerprint and a first link fingerprint, and according to the order of each of the special positive sequence suffixes in the first sequence and the first character of the suffix in the original character string character position, generate the first linked list for fingerprint verification, and generate the first fingerprint according to a plurality of said special positive sequence suffixes, including: According to the character type array, determine the character position of the suffix first character of each of the special positive sequence suffixes in the original character string; According to the descending order of the special positive sequence suffixes in the first order, sequentially write the plurality of special positive sequence suffixes into the corresponding temporary positions of each of the special positive sequence suffixes to generate a temporary linked list; the temporary The position is the adjacent position of the corresponding character position of the first character of each suffix in the original character string; Calculating the temporary positions of a plurality of said special positive sequence suffixes according to a fingerprint function to generate a first mobile fingerprint; According to the ascending order of the special positive sequence suffixes in the first order, sequentially write the multiple special positive sequence suffixes into the corresponding character positions of each of the special positive sequence suffixes to generate a first linked list; Calculating character positions of a plurality of said special positive sequence suffixes according to a fingerprint function to generate a first link fingerprint; The second linked list generation module is used to inductively sort a plurality of second suffixes about the second character type according to the first linked list, and determine the second order of the plurality of second suffixes; according to each of the second suffixes in the set The order in the second order and the character position of the first character of the suffix in the original character string, generate a second linked list for fingerprint verification, and generate a second fingerprint according to a plurality of the special positive sequence suffixes ; The second fingerprint is used to describe the first sequence of multiple special positive sequence suffixes when generating the second linked list; Wherein, the second character type includes a reverse sequence character and a positive sequence character, the corresponding second suffix includes a reverse sequence suffix and a positive sequence suffix, the second linked list includes a reverse sequence linked list and a positive sequence linked list, and the second sequence includes a reverse sequence suffix order and positive sequence suffix sequence, the second fingerprint includes positive sequence linked list fingerprints and reverse sequence linked list fingerprints, the plurality of second suffixes related to the second character type are sorted inductively according to the first linked list, and the plurality of second suffixes of the second character type are determined. The second order of the two suffixes; according to the order of each of the second suffixes in the second order and the character position of the first character of the suffix in the original character string, generate a second order for fingerprint verification Linked list, and generate the second fingerprint according to a plurality of said special positive sequence suffixes, including: determining the sequence of the reverse suffixes of the plurality of reverse suffixes according to the first linked list; According to the order of each of the reverse suffixes in the reverse suffix sequence and the character position of the first character of the suffix in the original character string, a reverse linked list and a fingerprint of the reverse linked list are generated; the fingerprint of the reverse linked list is used for Verifying the reverse linked list; determining the sequence of the positive sequence suffixes of the plurality of positive sequence suffixes according to the reverse sequence linked list; According to the order of each of the positive sequence suffixes in the positive sequence suffix sequence and the character position of the first character of the suffix in the original character string, a positive sequence linked list and a fingerprint of the positive sequence linked list are generated; The sequence linked list fingerprint is used to verify the positive sequence linked list; A suffix linked list generating module, configured to generate a suffix linked list corresponding to the original character string according to the second linked list of each of the second character types, and to generate the suffix linked list according to the first fingerprint and the second fingerprint Linked list for verification. 6. A terminal device, comprising a memory, a processor, and a computer program stored in the memory and operable on the processor, characterized in that, when the processor executes the computer program, the computer program according to claim The linked list generation method with its own verification function described in any one of 1-4. 7. A computer-readable storage medium, the computer-readable storage medium stores a computer program, characterized in that, when the computer program is executed by a processor, the self-contained Linked list generation method for validation functions.

Images