Problem 2.3.1 The Longest Prefix

출처: https://train.usaco.org/usacogate

---

문제 설명

출처 : IOI'96 - Problem 5

...

The first K characters of S are the prefix of S with length K. 

Write a program which accepts as input a set of primitives and a sequence of constituents and then computes the length of the longest prefix that can be composed from primitives. 

입력

First, the input file contains the list (length 1..200) of primitives (length 1..10) expressed as a series of space-separated strings of uppercase characters on one or more lines.

The list of primitives is terminated by a line that contains nothing more than a period (`.').

No primitive appears twice in the list.

 

Then, the input file contains a sequence S (length 1..200,000) expressed as one or more lines, none of which exceeds 76 letters in length.

 

The "newlines" (line terminators) are not part of the string S.

출력

A single line containing an integer that is the length of the longest prefix that can be composed from the set P.

입력 예

A AB BA CA BBC
.
ABABACABAABC

출력 예

11

---

문제 풀이

만들려고 하는 문자열 길이의 앞에서 부터 출발해서, 부분 문자열이 존재하는지 검사한다. 단순 double loop를 적용해도 부분 문자열의 수를 N, 만들려고 하는 문자열의 길이를 M이라고 하면 O(NM) 정도로 해결가능해진다.

프로그램 내용

... 
	// string target;
	// vector<string> primitives;
    
	dp[0]=1;
	for(int i=0;i< target.size();i++) 
	{
        if(dp[i])
        { 
            for(int j=0;j<primivites.size();j++) 
            {
                if( primivies[j]==target.substr(i,primitives[j].size()) ) 
                {
                    dp[i+primivies[j].size()] = 1;
                }
            }
        }
    }
    ...

 

Chapter 2. Bigger Challenges ( link )