소몰이꾼 시뮬레이션

소는 두 개의 문자열이 있습니다. (빈칸을 포함할 수 있습니다.) 소는 그 중에서 가장 긴 공공 연속 꼬치를 찾으려고 합니다. 당신이 그를 도와주고 길이를 출력해 주십시오.
설명 입력:

        （      ），       50.

출력 설명:

       ，             。

예를 입력합니다.

abcde
abgde

출력 예:

사고방식: LCS는 연속적일 수도 있고 불연속적일 수도 있다. 그들은 DP를 구성할 때 약간 다르다.
만약 연속적이라면 dp[i][j]는 s1의 전 i위와 s2의 전 j위가 가장 큰 공공 서브열을 맞출 수 있음을 나타낸다. 이렇게 해야만 연속 서브열의 조건을 만족시킬 수 있고 이전의 dp를 사용할 수 있다.
만약에 LCS가 연속되지 않는다면 dp[i][j]는 s1이 i까지, s2가 j까지 만족할 수 있는 최대치를 나타낸다
here is code

package l1;
import java.util.*;

/*
 * dp[i][j]   s1  i  s2  j            
 *            
 * 
 *          LCS   
 *          
 */
public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()) {
			String s1 = sc.nextLine(), s2 = sc.nextLine();
			
			int max = 0;
			int[][] dp = new int[s1.length()+1][s2.length()+1];
			for(int i=1; i<=s1.length(); i++)
				for(int j=1; j<=s2.length(); j++)
					if(s1.charAt(i-1) == s2.charAt(j-1)) {
						dp[i][j] = dp[i-1][j-1] + 1;
						max = Math.max(max, dp[i][j]);
					}
			
			System.out.println(max);
		}
	}

}

비연속 LCS 정보는 다음을 참조하십시오.http://blog.csdn.net/zjucor/article/details/65443719
소는 책에서 하나의 문자열을 회문열이라고 하는데, 하나의 문자열이 왼쪽에서 오른쪽으로 읽는 것과 오른쪽에서 왼쪽으로 읽는 것이 모두 같으면 이 문자열을 회문열이라고 부른다.소와 소는 또 친한 친구인 양과 양에게서 아름다운 문자열이라고 불리는 문자열을 알게 되었다. N은 대문자만 포함하는 문자열을 고려하여 모든 길이가 M인 연속 문자열(가능한 모든 시작 위치를 포함하는 문자열, 같은 문자열도 계산해야 한다)을 썼다. 만약에 이 문자열이 적어도 K 문자열이 모두 문자열이라면 우리는 이 문자열을 아름다운 문자열이라고 부른다.지금 N을 하나 주시오. 소는 길이가 N인 문자열이 얼마나 아름다운 답장꼬치인지 계산해 달라고 한다. (위치마다'A'~'Z'의 하나일 수 있다.)
설명 입력:

          N, M, K(2 ≤ N ≤ 11, 2 ≤ M ≤ N, 0 ≤ K ≤ 11).

출력 설명:

      ,          .

예를 입력합니다.

2 2 1

출력 예:

26
   2    ,    2        。   2     "AA","BB","CC"..."ZZ",  26 。

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

Java 프로그래머 면접에서의 다중 스레드 문제 요약

wait ()/notify ()/notify All () 의 모든 방법을 호출할 때, 현재 라인이 이 대상의 자물쇠를 얻지 못하면, Illegal MonitorState Exception의 이상을 던집니다. Thre...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

소몰이꾼 시뮬레이션

좋은 웹페이지 즐겨찾기