PIPIOJ 1039: repeat subsequence problem

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;
}

Keywords: C Algorithm Dynamic Programming

Added by phpbeginner0120 on Tue, 25 Jan 2022 03:36:59 +0200