★L(fēng)ongest Prefix 最長(zhǎng)前綴
在生物學(xué)中,一些生物的結(jié)構(gòu)是用包含其要素的大寫字母序列來表示的.生物學(xué)家對(duì)于把長(zhǎng)的序列
28
分解成較短的（稱之為元素的）序列很感興趣.
如果一個(gè)集合 P 中的元素可以通過串聯(lián)（允許重復(fù)；串聯(lián),相當(dāng)于 Pascal 中的 “+” 運(yùn)算符）
組成一個(gè)序列 S ,那么我們認(rèn)為序列 S 可以分解為 P 中的元素.并不是所有的元素都必須出現(xiàn).
舉個(gè)例子,序列 ABABACABAAB 可以分解為下面集合中的元素:
{A, AB, BA, CA, BBC}
序列 S 的前面 K 個(gè)字符稱作 S 中長(zhǎng)度為 K 的前綴.設(shè)計(jì)一個(gè)程序,輸入一個(gè)元素集合以及一個(gè)
大寫字母序列,計(jì)算這個(gè)序列最長(zhǎng)的前綴的長(zhǎng)度.
PROGRAM NAME: prefix
INPUT FORMAT
輸入數(shù)據(jù)的開頭包括 1..200 個(gè)元素（長(zhǎng)度為 1..10 ）組成的集合,用連續(xù)的以空格分開的字符串
表示.字母全部是大寫,數(shù)據(jù)可能不止一行.元素集合結(jié)束的標(biāo)志是一個(gè)只包含一個(gè) “.” 的行.集
合中的元素沒有重復(fù).接著是大寫字母序列 S ,長(zhǎng)度為 1..200,000 ,用一行或者多行的字符串來表
示,每行不超過 76 個(gè)字符.換行符并不是序列 S 的一部分.
SAMPLE INPUT (file prefix.in)
A AB BA CA BBC
ABABACABAABC
OUTPUT FORMAT
只有一行,輸出一個(gè)整數(shù),表示 S 能夠分解成 P 中元素的最長(zhǎng)前綴的長(zhǎng)度.
SAMPLE OUTPUT (file prefix.out)

11

我最怕就是對(duì)這種字符串進(jìn)行處理特別是換行之類的所以這題理所當(dāng)然放到最后寫，。。。。。。然后不會(huì)寫看了題解。。。。。。。

按順序找到該點(diǎn)能延伸到最遠(yuǎn)的那點(diǎn)并把那點(diǎn)標(biāo)記為true，再每找到true的點(diǎn)就往后延伸，直到找不到了因?yàn)槲覀兪前错樞蛘襱rue點(diǎn)的所以最后一個(gè)也就是最遠(yuǎn)的一個(gè)。

/*
ID:jinbo wu
LANG:C++
TASK:prefix
*/
#include<bits/stdc++.h>
using namespace std;
char a[205][15];
string str;
char s[100];
bool f[200010];
int main()
{freopen("prefix.in","r",stdin);freopen("prefix.out","w",stdout);int num=0,ans;scanf("%s",a[num]);while(a[num][0]!='.'){num++;scanf("%s",a[num]);	}str="";while(cin>>s)// cin>>s; str+=s;f[0]=true;for(int i=0;i<=str.length();i++){if(f[i]){   ans=i;for(int j=0;j<num;j++){int flag=1;for(int k=0;k<strlen(a[j]);k++)if(str[i+k]!=a[j][k]){flag=0;break;}if(flag)f[i+strlen(a[j])]=true;}}}cout<<ans<<endl;
}

總結(jié)

以上是生活随笔為你收集整理的usaco ★Longest Prefix 最长前缀的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。