【問題描述】
天蒼蒼，野茫茫，JSZX的菜鳥們來到OI牧場旅游，看到了好多好多的牛。OI牧場所有的牛都覺得自己的Rp最高（簡稱RP牛），為此他們常爭論不休。于是，他們讓JSZX的菜菜們用最最樸素的方法找出這只RP牛。
經(jīng)過討論，最菜的mmk想出了最樸素的方法：
我們要以cows的名字為線索，來找出RP牛。
首先，得到n頭牛的名字清單（每頭牛的名字是一個僅包含小寫字母的字符串，且這些牛的讀寫方式比較特殊—從右到左），然后對每頭牛進行檢驗，檢驗按照牛的讀寫方式進行。規(guī)則如下：
1．Rp 牛的名字中必須有子串“jszxoier”
2．將名字中的每個“cow”的替換為“bird”。
3．計算Rp值：A為名字中子串“r”的個數(shù)；
B為名字中子串“p”的個數(shù)；
C為名字中字串“rp”的個數(shù)；
Rp值即為5×A+5×B+20×C。
最后輸出RP牛的名字，若有多個RP牛，則輸出名字最短的那個。
假如你也是牛中一員，盡管你很不屑這樣的水題，但是，你很想到RP牛那里分點Rp，所以你決定解決這道題，并算出RP牛的Rp是多少。
【輸入】
第一行，一個數(shù)n（n<=3000）。
接下來的n行，每行一個字符串，長度<=300，數(shù)據(jù)保證存在RP牛。
【輸出】
共兩行
第一行為RP牛的名字
第二行為RP牛的Rp值
【樣例輸入】
8
reioxzsjzmy
mmk
jwc
zxf
jwc
wangwei
xcy
yuhc
【樣例輸出】
reioxzsjzmy
5
我用KMP匹配的，代碼挺短，還比string.h的好用。
1: #include <stdio.h>
2: #include <string.h>
3: #include <iostream>
4: #define maxn 400
5: using namespace std;
6:
7: int f[maxn];
8: char *aa="jszxoier",*bb="cow",*ee="rp",s[maxn];
9: int a,b,c,tem,ans,anslen,len,m;
10: int n;
11: bool t;
12: char anss[400];
13:
14: void initf(char *s)
15: {
16: memset(f,0,sizeof(f));
17: m=strlen(s);
18: int k=-1;
19: f[0]=-1;
20: for (int i=1;i<m;++i)
21: {
22: while ((k>-1)&&(s[k+1]!=s[i])) k=f[k];
23: if (s[k+1]==s[i]) ++k;
24: f[i]=k;
25: }
26: }
27:
28: void changef(char *s)
29: {
30: initf(s);
31: int k;
32: for (int i=0;i<m;++i)
33: {
34: k=f[i];
35: while ((k>-1)&&(s[k+1]==s[i+1])) k=f[k];
36: f[i]=k;
37: }
38: }
39:
40: int main()
41: {
42: freopen("input.txt","r",stdin);
43: freopen("output.txt","w",stdout);
44:
45: scanf("%d",&n);
46: for (int dt=1;dt<=n;++dt)
47: {
48: memset(s,0,sizeof(s));
49: scanf("%s",s);
50: strrev(s);
51: changef(aa);
52: len=strlen(s);
53: int k=-1;
54: t=0;
55: for (int i=0;i<len;++i)
56: {
57: while ((k>-1)&&(aa[k+1]!=s[i])) k=f[k];
58: if (aa[k+1]==s[i]) ++k;
59: if (k==m-1)
60: {
61: t=1;
62: break;
63: }
64: }
65: if (!t) continue;
66: a=b=c=0;
67: changef(bb);
68: for (int i=0;i<len;++i)
69: {
70: while ((k>-1)&&(bb[k+1]!=s[i])) k=f[k];
71: if (bb[k+1]==s[i]) ++k;
72: if (k==m-1) ++a;
73: }
74: for (int i=0;i<len;++i)
75: if (s[i]=='r') ++a;
76: for (int i=0;i<len;++i)
77: if (s[i]=='p') ++b;
78: changef(ee);
79: for (int i=0;i<len;++i)
80: {
81: while ((k>-1)&&(ee[k+1]!=s[i])) k=f[k];
82: if (ee[k+1]==s[i]) ++k;
83: if (k==m-1) ++c;
84: }
85: tem=a*5+b*5+c*20;
86: if (tem>ans)
87: {
88: memset(anss,0,sizeof(anss));
89: strcat(anss,s);
90: ans=tem;
91: anslen=len;
92: }
93: else
94: if (tem==ans)
95: if (len<anslen)
96: {
97: memset(anss,0,sizeof(anss));
98: strcat(anss,s);
99: }
100: }
101: strrev(anss);
102: printf("%s\n%d\n",anss,ans);
103: return 0;
104: }
105: