HDU 6774 String Distance(시퀀스 로봇 + dp)

16922 단어 #단순문자열
제목: 두 개의 문자열 a(1e5)와 b(20)를 제시하고 q개의 질문 구간 l, r를 제시하며 문자열 a에서 r로 표시하는 하위 문자열을 b로 바꾸려면 최소 몇 번의 조작이 필요하며 매번 조작은 한 문자를 삽입하거나 삭제하는 것으로 한정됩니다.
문제풀이: 서열자동기기+dp가 한 문자열 a[l,r] a[l,r] a[l,a[l,r] a[l,r]a[l,r]a[l,r]a[l,r]a[l,r]가 다른 문자열 bbbb로 변한다. 우리는 먼저 두 줄의 lcslcslcs lcs를 구할 수 있다. 먼저 aaaaaa에서 lcslcslcs가 아닌 r-4-l+1로 r-l csr-l+1-l cr-l+1-l+1-lcs를 삭제하고 bbbbbbbb와 같게 해서 모두 m-l csmm-lcs로 되어 있어 r-l++l+l+l+ 1l+ 1l+l+ll+ 1llll+ 2lll+ +m-2*lcs r-3 l+1 +m-3 2∗lcs.
다음은 어떻게 비교적 짧은 시간에 lcslcslcs를 구할 것인가를 고려한다.정상적인 구법은 틀림없이 안 된다. 우리는 bbb의 길이가 20에 불과하다는 것을 발견할 수 있다. 그러면 lcslcslcs는 많으면 20이다.그래서 우리는 dp[i][len]=jdp[i][len]=jdp[i]=j]=j를 설정하여 a[l,j]a[l,j]a[l,j]와 b[1,i]b[1,i]b[1,i]의 lcslcslcslcs 길이는 lenlen이다.
그러나 이렇게 하려면 반드시 aa열이 위치 ii에서 지정한 문자의 가장 가까운 위치를 미리 처리해야 한다. 우리는 서열 자동기로 구하면 된다. nxt[i][j]nxt[i][j]nxt[i][j]는 ii부터 문자 jj의 가장 가까운 위치를 나타낸다.
그러면 우리는 전이 방정식을 얻을 수 있다. dp[i][j] = min(dp[i][j], nxt[dp[i - 1][j - 1] + 1][b[i] - 97]); 그리고 dp값이 바로 오른쪽 단점이 r안에 있으면lcs이다.
#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
using namespace std;
const int maxn = 1e5 + 5;
char a[maxn], b[22];
int t, q, l, r, la, lb, nxt[maxn][26], dp[22][22];
int main() {
	scanf("%d", &t);
	while (t--) {
		scanf("%s%s", a + 1, b + 1);
		la = strlen(a + 1);
		lb = strlen(b + 1);
		for (int i = 0; i < 26; i++) nxt[la + 1][i] = la + 1;
		for (int i = la; i >= 1; i--) {
			for (int j = 0; j < 26; j++) nxt[i][j] = nxt[i + 1][j];
			nxt[i][a[i] - 97] = i;
		}
		scanf("%d", &q);
		while (q--) {
			scanf("%d%d", &l, &r);
			for (int i = 1; i <= lb; i++) dp[0][i] = la + 1; //   
			dp[0][0] = l - 1;  //    
			for (int i = 1; i <= lb; i++) {
				dp[i][0] = l - 1; //   
				for (int j = 1; j <= lb; j++) {
					dp[i][j] = dp[i - 1][j];
					if (dp[i - 1][j - 1] < r)
						dp[i][j] = min(dp[i][j], nxt[dp[i - 1][j - 1] + 1][b[i] - 97]);
				}
			}
			int lcs = 0;
			for (int i = lb; i >= 1; i--) {
				if (dp[lb][i] <= r) {
					lcs = i;
					break;
				}
			}
			printf("%d
", r - l + 1 + lb - 2 * lcs);
		}
	}
	return 0;
}
JPA에서 setParameter에% (와일드카드 문자) 의 like 문장을 포함합니다
Java의 파일 복사 기록

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage