【问题描述】
天苍苍，野茫茫，JSZX的菜鸟们来到OI牧场旅游，看到了好多好多的牛。OI牧场所有的牛都觉得自己的Rp最高（简称RP牛），为此他们常争论不休。于是，他们让JSZX的菜菜们用最最朴素的方法找出这只RP牛。
经过讨论，最菜的mmk想出了最朴素的方法：
我们要以cows的名字为线索，来找出RP牛。
首先，得到n头牛的名字清单（每头牛的名字是一个仅包含小写字母的字符串，且这些牛的读写方式比较特殊—从右到左），然后对每头牛进行检验，检验按照牛的读写方式进行。规则如下：
1．Rp 牛的名字中必须有子串“jszxoier”
2．将名字中的每个“cow”的替换为“bird”。
3．计算Rp值：A为名字中子串“r”的个数；
B为名字中子串“p”的个数；
C为名字中字串“rp”的个数；
Rp值即为5×A+5×B+20×C。
最后输出RP牛的名字，若有多个RP牛，则输出名字最短的那个。
假如你也是牛中一员，尽管你很不屑这样的水题，但是，你很想到RP牛那里分点Rp，所以你决定解决这道题，并算出RP牛的Rp是多少。
【输入】
第一行，一个数n（n<=3000）。
接下来的n行，每行一个字符串，长度<=300，数据保证存在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: