1039: repeat subsequence problem
Title Description
PIPI has two strings a and B. please find out how many times the string a is repeated at least to make B a subsequence of A.
We call x a subsequence of Y if and only if several characters can be deleted from Y to get X.
For example, for A = "abb" and B="bbaa", A repeats 3 times to get "abbabbabbab". At this time, B="bbaa" is A subsequence of "abbabbabbab".
Note that the original string A is counted as A repeat.
input
Multiple sets of data.
The first line contains A string A.
The second line contains a string B.
Both A and B contain only lowercase letters.
For 30% data, 1 < = | a |, | B | < = 100
For 90% of the data, 1 < = | a |, | B | < = 1000
For 100% data, 1 < = | a |, | B | < = 100000
output
An integer represents the answer. If it cannot be reached no matter how many times it is repeated, output - 1.
sample input
abb bbaa
sample output
3
thinking
This problem is intuitive. Traverse B and find the same character as B's current position in A. if not, repeat an A and find it from scratch. The complexity of finding the elements in B in a is o (n), the total complexity of the algorithm is o (n * m), and N and m are the lengths of a and B respectively. For 100% data, 1 < = | a |, | B | < = 100000. In the worst case, it will definitely timeout (e.g. a = "99999 ba", B = "100000 a"). Therefore, using sequential automata, we can find out whether there are characters at the corresponding position in B in a in o (1). The time complexity of the algorithm is o (max (n, m)).
Sequential automata
Sequential automata is an algorithm that can quickly judge whether any sequence t contains subsequence s, space for time. (we call X a subsequence of Y if and only if several characters can be deleted from Y to get X)
Idea: construct an NXT array for sequence s, nxt[i] [j] represents the alphabet after the ith position in sequence s Σ The first occurrence of the j-th element in. For example: Σ= {0,1},s = “1001”,nxt[4] = {0,0},nxt[3] = {0,4},nxt[2] = {3,4},nxt[1] = {2,4},nxt[0] = {2,1}.
Specific implementation:
//Construct nxt array int nxt[N][2]; string s = "#1001"; int len = s.length() - 1; // Initialize nxt[len]. At this time, there is no character after the len character in s. 0 -- indicates that the character does not appear for(int i = 0; i < 2; i++) nxt[len][i] = 0; for(int i = len; i > 0; i--) { for(int j = 0; j < 2; j++) nxt[i - 1][j] = nxt[i][j]; nxt[i - 1][s[i] - '0'] = i; } //lookup // Find subsequence string str = "#001"; int p = 0; for(int i = 1; i <= str.length(); i++) { p = nxt[p][str[i] - '0']; if(p == 0) printf("No subsequence exists.\n"); }
Answer to this question:
#include<bits/stdc++.h> using namespace std; const int N = 100000 + 3; char a[N], b[N]; int nxt[N][26]; // Sequential automata int main() { while(scanf("%s\n%s", a + 1, b) != EOF) { // Building nxt arrays int lena = strlen(a + 1), lenb = strlen(b); for(int i = 0; i < 26; i++) nxt[lena][i] = 0; for(int i = lena; i > 0; i--) { for(int j = 0; j < 26; j++) nxt[i - 1][j] = nxt[i][j]; nxt[i - 1][a[i] - 'a'] = i; } /* Shilling p = -1, find b[i] in a in turn, which is equivalent to p = nxt[p + 1][b[i] - 'a'] If p = 0, it means that there is no b[i] in A. repeat a again */ // If there are characters in b but not in a, no matter how many times a repeats, b cannot be a subsequence bool flag = false; for(int i = 0; i < lenb; i++) { if(nxt[0][b[i] - 'a'] == 0) { flag = true; break; } } if(flag) { puts("-1"); continue; } int ans = 1; int p = 0; for(int i = 0; i < lenb; i++) { p = nxt[p][b[i] - 'a']; if(p == 0) { p = nxt[p][b[i] - 'a']; ans++; } } printf("%d\n", ans); } return 0; }