Longest Prefix - USACO 2.3.1

thelongestprefix - codetrick
The structure of some biological objects is represented by the sequence of their constituents denoted by uppercase letters. Biologists are interested in decomposing a long sequence into shorter ones called primitives.
We say that a sequence S can be composed from a given set of primitives P if there is a some sequence of (possibly repeated) primitives from the set whose concatenation equals S. Not necessarily all primitives need be present. For instance the sequence ABABACABAABcan be composed from the set of primitives

  {A, AB, BA, CA, BBC}  

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.

PROGRAM NAME: prefix

INPUT FORMAT

First, the input file contains the list (length 1..200) of primitives (length 1..10) expressed as a series of space-separated strings of upper-case 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 exceed 76 letters in length. The "newlines" are not part of the string S.

SAMPLE INPUT (file prefix.in)

A AB BA CA BBC  .  ABABACABAABC  

OUTPUT FORMAT

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

SAMPLE OUTPUT (file prefix.out)

11

Given a set of strings P and a larger string S, find the length of the longest prefix of S that can be made from the concatenation of (possibly repeating) strings from P.
https://www.byvoid.com/blog/usaco-231-longest-prefix

定义dp[i]为串S中从第i位开始的串的最长前缀的长度,根据题目要求,结果输出 dp[0] (从第0位开始到len(S)-1的串的最长前缀的长度)

定义fd(i)为//主串S中以第i位开始的字串,向后比较匹配集合中元素的最大长度

倒序递推: 从i=lens-1 到 i=0

• fd(i)=0
• dp [i]=0
• fd(i)=k(k>0)
• dp [i]=dp[i+j]+j (1<=j<=k-1;dp[i+j]!=0)
• 如果不满足上式dp [i]=dp[i+k]+k

http://qingtangpaomian.iteye.com/blog/1635387
我们使用数组result[i]=1表示字符串S中从1到i的所有字符都可以由集合P中元素组成。那么如果要result[i]=1，那么条件是result[j]=1（j<i），并且字符串S中j到i的字符在集合P中。

1.         HashSet<String> prefix = new HashSet<String>();  
2.         String line = in.readLine();  
3.         while(!line.equals(".")){  
4.             StringTokenizer tokens = new StringTokenizer(line);  
5.             while(tokens.hasMoreTokens()){  
6.                 prefix.add(tokens.nextToken());   
7.             }  
8.             line = in.readLine();  
9.         }  
10.         StringBuffer tmpS = new StringBuffer();  
11.         String readLine2 = in.readLine();  
12.         while (readLine2 != null)  
13.         {  
14.             tmpS.append(readLine2);  
15.             readLine2 = in.readLine();  
16.         }  
17.         line = " "+tmpS.toString();  
18.           
19.         int[] result = new int[line.length()];  
20.         result[0] = 1;  
21.         String temp;  
22.         int cnt = 0;  
23.         for (int i=1;i<line.length();i++){  
24.             for (int j=i;j>=1;j--){  
25.                 if (i-j+1>10){  
26.                     break;  
27.                 }  
28.                 temp = line.substring(j, i+1);  
29.                 if (prefix.contains(temp)){  
30.                     if (result[j-1]==1){  
31.                         result[i] = 1 ;  
32.                         break;  
33.                     }  
34.                 }  
35.             }  
36.         }  

http://www.dlifep.com/?p=100

X. Trie https://13codes.wordpress.com/2013/05/13/usaco-longest-prefix/

我用trie树来存小字符串集合  扫描大字符串时  如果该位置是可以向后延伸的（即之前能拼到这个位置）

那么我用一个标记在trie树上爬  每次发现一个小字符串结束标志  就表示对应大字符串的位置是可延伸的

这样做下标记并更新答案

http://www.cnblogs.com/yewei/archive/2012/08/06/2625745.html

void Trie::Trie_Find( long j )
 90 {
 91     Trie_Node *ptr = root;
 92     for ( ; ; ++j )
 93     {
 94         ptr = ptr->branch[ ss[j]-'A' ];
 95         if ( ss[j]=='\0' || ptr==NULL )
 96             return ;
 97         if ( ptr->IsEnd )
 98             prefix[ j+1 ]=true;
 99     }
100     
101     return ;
102 }// Trie_Find
103 
104 void Solve()
105 {
106     prefix[0] = true;
107     for ( long i=0; i<slen; ++i )
108     {
109         if ( !prefix[i] )   continue;
110         
111         t.Trie_Find( i );
112     }// Searching
113     
114     int result;
115     for ( result=slen; !prefix[result]; --result );
116     printf("%d\n", result);
117 
118     return ;
119 }// Solve

X. AC自动机

AC自动机。先根据给出的模式串建树，然后与被匹配串进行匹配。

建立一个T_len[]数组，T_len[i]==x表示以T[i]为首匹配的单词的最大长度为x。求出T_len[]，就可以推导出答案，具体过程见solved()函数。

每次与模式串匹配成功时，都对T_len[]进行更新。当匹配结束，则T_len[]也更新完毕。

例如T[i]结尾的单词与长度为len的模式串匹配成功，则比较T_len[i-(len-1)]与len的大小，取两者中的较大值。其中i-(len-1)表示模式串在被匹配串中的匹配位置。

X. BFS
http://www.boyu0.com/usaco-longest-prefix/
我采用的是bfs穷搜的暴力方法，用字典树存储所有的元素，在每个元素的终结节点做一个mark，然后从头开始搜索字典树，使用一个队列保留状态，每输入一个字符，更新一次队列上的所有状态，弹出所有不能往下搜索的状态，当到达mark节点时加入字典树根节点状态（从头开始搜索），直到队列为空（或者到达字符串结尾），最后到达的mark节点即是所能组成的最长前缀。
http://java-mans.iteye.com/blog/1646874
http://sdjl.me/index.php/archives/89
Read full article from thelongestprefix - codetrick