gzwzm06

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
更好的方法:后缀数组 + 栈扫描

我的程序还可以在优化下:记录当前的长度,不去搜索比它小的子串
  1#include <cstdio>
  2#include <cstring>
  3
  4const int STRNUM = 10 ;
  5const int SIZE = 62 ;
  6
  7char str[STRNUM][SIZE] ;
  8int N ;
  9
 10int next[STRNUM][SIZE] ;
 11
 12bool FindSubstr( const int& k, const char* des )
 13{
 14    int i = 0 , j = 0 , srcLen = strlen(str[k]) , desLen = strlen(des) ;
 15
 16    while ( i < srcLen && j < desLen )
 17    {
 18        if ( j == -1 || str[k][i] == des[j] )
 19        {
 20            i++ ;
 21            j++ ;
 22        }

 23        else j = next[k][j] ;
 24    }

 25
 26    if ( j >= desLen )
 27        return true ;
 28    else
 29        return false ;
 30}

 31
 32void GetNext()
 33{
 34
 35    for ( int i = 0 ; i < N ; ++i )
 36    {
 37        int j = 0 , k = -1 ;
 38
 39        next[i][0= -1 ;
 40
 41        while ( j < (int)strlen(str[i]) )
 42        {
 43            if ( k == -1 || str[i][j] == str[i][k] )
 44            {
 45                j++ ;
 46                k++ ;
 47                next[i][j] = k ;
 48            }

 49            else
 50                k = next[i][k] ;
 51        }

 52    }

 53}

 54
 55void Solve()
 56{
 57    int i , j , k ;
 58
 59    int len = (int)strlen(str[0]) ;
 60    char temp[SIZE] ;
 61
 62    bool ok = false ;
 63    char result[SIZE] ;
 64    int rLen ;
 65
 66    GetNext() ;
 67
 68    for ( i = 0 ; i < len - 2 ; ++i )
 69    {
 70        for ( j = i , k = 0 ; j < len ; ++j , ++k )
 71            temp[k] = str[0][j] ;
 72
 73        for ( j = k ; j > 2 ; --j )
 74        {
 75            temp[j] = '\0' ;
 76
 77            for ( k = 1 ; k < N ; ++k )
 78            {                
 79                if ( !FindSubstr( k, temp ) )
 80                {
 81                    break ;
 82                }

 83            }

 84
 85            if ( k == N )
 86            {
 87                if ( ok )
 88                {
 89                    int tLen = (int)strlen(temp) ;
 90                    if ( tLen > rLen || (tLen == rLen && strcmp(temp, result) < 0) )
 91                    {
 92                        rLen = tLen ;
 93                        strcpy( result, temp ) ;
 94                    }

 95                }

 96                else
 97                {
 98                    ok = true ;
 99                    strcpy( result, temp ) ;
100                    rLen = (int)strlen(result) ;
101                }

102            }

103
104        }

105    }

106
107    if ( ok )
108    {
109        printf("%s\n", result) ;
110    }

111    else {
112        printf("no significant commonalities\n") ;
113    }

114
115}

116
117void Input()
118{
119    int i , n , m ;
120
121    scanf("%d"&n) ;
122
123    while ( n-- )
124    {
125        scanf("%d"&m) ;
126
127        N = m ;
128
129        getchar() ;
130
131        for ( i = 0 ; i < m ; ++i )
132        {
133            gets(str[i]) ;
134        }

135
136        Solve() ;
137    }

138
139}

140
141int main()
142{
143//    freopen("1.txt", "r", stdin) ;
144
145    Input() ;
146
147    return 0 ;
148}
posted on 2009-03-09 12:51 阅读(339) 评论(0)  编辑 收藏 引用 所属分类: 字符串处理

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理