ACM水题－－字符串的前缀和后缀ACM水题－－字符串的前缀和后缀
2012-03-09 17:15 779人阅读评论(0) 收藏举报
stringoutputinputc
[cpp]view plaincopy?
1. 字符串的前缀和后缀
2.
3. Time Limit:1000MS Memory Limit:65536K
4. Total Submit:81 Accepted:22
5.
6. Description
7.
8. 字符串的前缀是指字符串的任意首部。比如字符串“abbc”的前缀有“a”,“ab”,“abb”,“abbc”。
同样，字符串的任意尾部是字符串的后缀，“abbc”的后缀有“c”,“bc”,“bbc”,“abbc”。现在给出一些字符串，找出每个字符串中含字符种类最多的前缀或后缀。
9.
10. Input
11.
12. 输入第一行是一个整数n(1<=n<=50)，表示有n个字符串。
13. 下面有n行，每行的格式是这样：字符串str 字符ch
14. 字符串str由小写字母组成，长度不超过100000，字符ch只有两个取值’P’,’S’。
15. 如果ch为’P’，则找出含字符种类最多的前缀。如果ch为’S’，则找出含字符种类最多的后缀。
16.
17.
18. Output
19.
20. 对于每个字符串，输出一行。
stamp21. 输出格式是这样：String #X: Yaleph
22. 按字符串的读入顺序，X从1开始递增到n。
23. Y是满足条件的前缀字符串或后缀字符串，
24. 如果有多个前缀或后缀满足条件，则取长度最小的一个。
25.
26.
27. Sample Input
28.
29.
30. 3
31. abbc P
32. kaaaaaaaaaa P
33. nlogn S
34.
35.
36. Sample Output
37.
38.
39. String #1: abbc
40. String #2: ka
41. String #3: logn
42.
43. Source
44.
45. cxyue
[cpp]view plaincopy?
1. /* -----------------------------------------------------------------------------------
2. 大概想法：
3.
4. 举例：
5. 情景：当选择为P时
6.
7. 思路：1.字符串头尾各设一个指针，将两个指针所指向的值作比较，直到两个指针所针
的地址相同
8. 2.若头指针所指的字符与尾指针相等，则尾指针向前移一位，头指针重置为第一位，
重复1
9. 3.若头指针所指的字符与尾指针不相等，则头指针向前移一位，重复1
10.
11.
车辆保养知识12. 结果： Accept，时间太弱了.......不过，自己还是没有想到可以更快的方法.
13. ----------------------------------------------------------------------------------- */
14.
15.
16.
17. #include<stdio.h>
18. #include<string.h>
19.
20. void Find(char *szStr, int n, char choice) ;
21.
22. char szInputStr[100000] ;ned
23.
24. int main(void)
25. {
26. int i = 1 ;
27. int t = 0 ;
28.
29. char chChoice = 0 ;
语音翻译在线
30.
31. scanf("%d",&t) ;
32.
美国招生
33. while(getchar() != '\n')
34. {
35. continue ;
36. }
37.
38. while(t-- > 0)
39. {
40. scanf("%s %c",szInputStr,&chChoice) ;
41. Find(szInputStr,i++,chChoice) ;
42. }
43.
杨格外语44. return 0 ;
45. }
46.
47.
48. void Find(char *szStr , int n, char choice)
49. {
50. char *pszBeg = szStr ;
51. char *pszEnd = szStr + strlen(szStr) - 1 ;
52. char szOutputStr[1000] ;
53.
54. char *pEndPos = pszEnd ;
55. char *pBegPos = pszBeg ;
56.
57. int iLen = strlen(szStr) ;
58.
59. if('P' == choice)
60. {
61. while(pszBeg != pszEnd)
62. {
63. if(*pszBeg == *pszEnd)
64. {
65. pszEnd-- ;
66. pEndPos = pszEnd ;
67. pszBeg = szStr ;
68. }
69. el
70. {
71. pszBeg++ ;fater
72. }
73. }
74.
75. iLen = pEndPos - szStr + 1 ;
76. strncpy(szOutputStr, szStr, iLen) ;
77. szOutputStr[iLen] = '\0' ;
78. }
79. el if('S' == choice)
80. {
81. while(pszBeg != pszEnd)
82. {
83. if(*pszBeg == *pszEnd)
84. {
85. pszBeg++ ;
86. pBegPos = pszBeg ;
87. pszEnd = szStr + iLen - 1 ;
88. }
89. el
90. {
91. pszEnd-- ;
92. }
桀骜不驯怎么读93. }
94.
95. pszEnd = szStr + iLen - 1 ;
肖克申的救赎96. iLen = pszEnd - pBegPos + 1 ;
97. strncpy(szOutputStr, pBegPos, iLen) ;
98. szOutputStr[iLen] = '\0' ;
99. }
100.
101. printf("String #%d: %s\n",n,szOutputStr) ; 102. }
