其实这个题的思路和简单:找到最短的一个串,然后再找到他所有的子串和子串的逆串和所给的串进行匹配。
但是如果不直接调用string.h的函数实现这些功能,我自己就不知道做;
感觉String.h 有好多功能自己不了解,像strstr() strncpy() strrev()可是poj系统不支持这个函数
1
#include <stdio.h>
2
#include <string.h>
3
char str[100][101];
4![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
5
int t, n;
6
void strrev (char *revString)
7![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
8
int revLen = strlen (revString);
9
char temp[101];
10
11
int i;
12
for ( i = 0; i < revLen; i ++)
13![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
14
temp[i] = revString[revLen - i - 1];
15
}
16
temp [i] = '\0';
17
strcpy (revString, temp);
18
}
19![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
20
int searchSubString (char *source)
21![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
22
char minSubString[101];
23
char minrevSubString[101];
24![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
25
int minSubStringLen = strlen (source);
26
int sourceLen = strlen (source);
27![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
28
while (minSubStringLen)
29![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
30
for (int i = 0; i <= sourceLen - minSubStringLen; i ++)
31![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
32
bool tag = true;
33
strncpy (minSubString, source + i, minSubStringLen);
34
strncpy (minrevSubString, source + i, minSubStringLen);
35![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
36
minSubString[minSubStringLen] = minrevSubString[minSubStringLen] = '\0';
37![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
38
strrev (minrevSubString);
39![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
40
for (int i = 0; i < n; i ++)
41![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
42
if ( strstr (str[i], minSubString) == NULL && strstr (str[i], minrevSubString) == NULL )
43![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
44
tag = false;
45
break;
46
}
47
}
48![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
49
if (tag)
50
return minSubStringLen;
51
}
52
minSubStringLen --;
53
}
54![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
55
return 0;
56
}
57![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
58
int main ()
59![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
60
61
char minStr[101];
62![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
63
scanf ("%d", &t);
64
while ( t != 0 )
65![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
66
scanf ("%d", &n);
67![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
68
int minStrlen = 100;
69
for (int i = 0; i < n; i ++)
70![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
71
scanf ("%s", str[i]);
72
if ( ( strlen(str[i]) ) < minStrlen )
73![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
74
strcpy(minStr, str[i]);
75
minStrlen = strlen (str[i]);
76
}
77
}
78![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
79
int minSubLen = searchSubString (minStr);
80
printf ("%d\n", minSubLen);
81![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
82
t --;
83
}
84
return 0;
85
}
posted on 2010-08-06 11:50
雪黛依梦 阅读(298)
评论(0) 编辑 收藏 引用 所属分类:
字符串处理题