其實這個題的思路和簡單：找到最短的一個串，然后再找到他所有的子串和子串的逆串和所給的串進行匹配。
但是如果不直接調用string.h的函數實現這些功能，我自己就不知道做；
感覺String.h 有好多功能自己不了解，像strstr() strncpy() strrev()可是poj系統不支持這個函數
1
#include <stdio.h>
2#include <string.h>
3char str[100][101];
4
5int t, n;
6void strrev (char *revString)
7
{
8
int revLen = strlen (revString);
9 char temp[101];
10
11 int i;
12 for ( i = 0; i < revLen; i ++)
13
{
14 temp[i] = revString[revLen - i - 1];
15
}
16 temp [i] = '\0';
17 strcpy (revString, temp);
18
}
19
20int searchSubString (char *source)
21{
22 char minSubString[101];
23 char minrevSubString[101];
24
25 int minSubStringLen = strlen (source);
26 int sourceLen = strlen (source);
27
28 while (minSubStringLen)
29 {
30 for (int i = 0; i <= sourceLen - minSubStringLen; i ++)
31 {
32 bool tag = true;
33 strncpy (minSubString, source + i, minSubStringLen);
34 strncpy (minrevSubString, source + i, minSubStringLen);
35
36 minSubString[minSubStringLen] = minrevSubString[minSubStringLen] = '\0';
37
38 strrev (minrevSubString);
39
40 for (int i = 0; i < n; i ++)
41 {
42 if ( strstr (str[i], minSubString) == NULL && strstr (str[i], minrevSubString) == NULL )
43 {
44 tag = false;
45 break;
46 }
47 }
48
49 if (tag)
50 return minSubStringLen;
51 }
52 minSubStringLen --;
53 }
54
55 return 0;
56}
57
58int main ()
59{
60
61 char minStr[101];
62
63 scanf ("%d", &t);
64 while ( t != 0 )
65 {
66 scanf ("%d", &n);
67
68 int minStrlen = 100;
69 for (int i = 0; i < n; i ++)
70 {
71 scanf ("%s", str[i]);
72 if ( ( strlen(str[i]) ) < minStrlen )
73 {
74 strcpy(minStr, str[i]);
75 minStrlen = strlen (str[i]);
76 }
77 }
78
79 int minSubLen = searchSubString (minStr);
80 printf ("%d\n", minSubLen);
81
82 t --;
83 }
84 return 0;
85}
posted on 2010-08-06 11:50
雪黛依夢 閱讀(322)
評論(0) 編輯 收藏 引用 所屬分類:
字符串處理題