Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

   最近一直在准备省赛,基本都是复习算法和组队赛,基本没切什么题. 昨天想省赛前POJ刷到1200先,就跟光光对拍了下POJ过的题. 发现了这道字符串,顺便复习下KMP和后缀数组啥的.
       这题跟POJ 3080基本完全一样,当年写过个解题报告 http://www.cppblog.com/Uriel/articles/98530.html
       那时候还不会后缀数组,就用KMP和strstr两种方法水过去了. POJ 3450这题大概数据也不是很强吧...用KMP和strstr也都可以过的.
   今天又试了下后缀数组,速度好慢... = = 
       后缀数组代码参考了 http://www.cnblogs.com/ltang/archive/2010/11/30/1891708.html
       发现罗穗骞论文的代码里calheight那个函数数组下标那里可能会越界...,还请路过的大牛们指教.现在是照着上面那个Blog里的代码改了

       各算法运行时间如下:
       KMP: C++ 1469Ms
       strstr: C++ 969Ms

       Suffix Array (DA): C++ 1063Ms G++ 875Ms
   Suffix Array (DC3): C++ 1063Ms

       各算法的代码如下:

       KMP

/*
 * Problem: 3450  User: Uriel 
 * Memory: 8424K  Time: 1469MS 
 * Language: C++  Result: Accepted 
 
*/

#include
<stdio.h>
#include
<stdlib.h>
#include
<string.h>
#include
<algorithm>

using namespace std;

int start, n, nxt[210];
char str[40010][210];

struct P {
    
char res[210];
}
 Ans[4100];

char dest[100];

bool cmp(P a, P b) {
    
return strcmp(a.res, b.res) < 0;
}


void GetNext(char* str) {
    nxt[
0= -1;
    
int i = 0, j = -1;
    
while (str[i]) {
        
if (j == -1 || str[i] == str[j]) {
            i
++;
            j
++;
            nxt[i] 
= j;
        }
 else
            j 
= nxt[j];
    }

}


int kmpMatch(char* Src, char* Dest) {
    
int i = 0, j = 0, s_len, p_len, sum = 0;
    s_len 
= strlen(Src);
    p_len 
= strlen(Dest);
    M: 
while (i < s_len && j < p_len) {
        
if (j == -1 || Src[i] == Dest[j]) {
            
if (j == p_len - 1)
                
return i - p_len + 1;
            i
++;
            j
++;
        }
 else
            j 
= nxt[j];
    }

    
return -1;
}


void Sov() {
    
int i;
    
for (i = 1; i < n; i++{
        
if (kmpMatch(str[i], dest) == -1{
            start 
= 1;
            
return;
        }

    }

    
return;
}


int main() {
    
int i, j, k, s, len;
    
while (scanf("%d"&n), n) {
        scanf(
"%d"&n);
        memset(str, 
0x00sizeof(str));
        
for (i = 0; i < n; i++)
            scanf(
"%s", str[i]);
        len 
= strlen(str[0]);
        s 
= 0;
        
for (i = len; i >= 1; i--{
            j 
= 0;
            
while (j + i <= len) {
                start 
= 0;
                memset(dest, 
0x00sizeof(dest));
                strncpy(dest, 
&str[0][j], i);
                GetNext(dest);
                Sov();
                
if (!start) {
                    strcpy(Ans[s
++].res, dest);
                }

                j
++;
            }

            
if (s)
                
break;
        }

        
if (s) {
            sort(Ans, Ans 
+ s, cmp);
            printf(
"%s\n", Ans[0].res);
        }
 else {
            puts(
"IDENTITY LOST");
        }

    }

    
return 0;
}


   strstr

/*
 * Problem: 3450  User: Uriel 
 * Memory: 8424K  Time: 969MS 
 * Language: C++  Result: Accepted 
 
*/

#include
<stdio.h>
#include
<stdlib.h>
#include
<string.h>
#include
<algorithm>

using namespace std;

int start, n;
char str[40010][210];

struct P {
    
char res[210];
}
 Ans[4100];

char dest[100];
int Next[100];

bool cmp(P a, P b) {
    
return strcmp(a.res, b.res) < 0;
}


void Sov() {
    
int i;
    
for (i = 1; i < n; i++{
        
if (strstr(str[i], dest) == NULL) {
            start 
= 1;
            
return;
        }

    }

    
return;
}


int main() {
    
int i, j, k, s, len;
    
while (scanf("%d"&n), n) {
        scanf(
"%d"&n);
        memset(str, 
0x00sizeof(str));
        
for (i = 0; i < n; i++)
            scanf(
"%s", str[i]);
        len 
= strlen(str[0]);
        s 
= 0;
        
for (i = len; i >= 1; i--{
            j 
= 0;
            
while (j + i <= len) {
                start 
= 0;
                memset(dest, 
0x00sizeof(dest));
                strncpy(dest, 
&str[0][j], i);
                Sov();
                
if (!start) {
                    strcpy(Ans[s
++].res, dest);
                }

                j
++;
            }

            
if (s)
                
break;
        }

        
if (s) {
            sort(Ans, Ans 
+ s, cmp);
            printf(
"%s\n", Ans[0].res);
        }
 else {
            puts(
"IDENTITY LOST");
        }

    }

    
return 0;
}

       Suffix Array (DA)
/*
 * Problem: 3450  User: Uriel 
 * Memory: 3604K  Time: 875MS 
 * Language: G++  Result: Accepted 
 
*/

#include
<stdio.h>
#include
<stdlib.h>
#include
<string.h>
#define N 1000000
int n, r[N], sa[N];
int wa[N], wb[N], wv[N], ws[N];

int cmp(int *r, int a, int b, int l) {
    
return r[a] == r[b] && r[a + l] == r[b + l];
}

void da(int *r, int *sa, int n, int m) {
    
int i, j, p, *= wa, *= wb, *t;
    
for (i = 0; i < m; i++)
        ws[i] 
= 0;
    
for (i = 0; i < n; i++)
        ws[x[i] 
= r[i]]++;
    
for (i = 1; i < m; i++)
        ws[i] 
+= ws[i - 1];
    
for (i = n - 1; i >= 0; i--)
        sa[
--ws[x[i]]] = i;
    
for (j = 1, p = 1; p < n; j *= 2, m = p) {
        
for (p = 0, i = n - j; i < n; i++)
            y[p
++= i;
        
for (i = 0; i < n; i++)
            
if (sa[i] >= j)
                y[p
++= sa[i] - j;
        
for (i = 0; i < n; i++)
            wv[i] 
= x[y[i]];
        
for (i = 0; i < m; i++)
            ws[i] 
= 0;
        
for (i = 0; i < n; i++)
            ws[wv[i]]
++;
        
for (i = 1; i < m; i++)
            ws[i] 
+= ws[i - 1];
        
for (i = n - 1; i >= 0; i--)
            sa[
--ws[wv[i]]] = y[i];
        
for (t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; i++)
            x[sa[i]] 
= cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++;
    }

    
return;
}

int rank[N], height[N];
void calheight(int *r) {
    
int i, j, k;
    
for (i = 0; i < n; i++)
        rank[sa[i]] 
= i;
    
for (i = 0, height[0= k = 0; i < n; height[rank[i++]] = k)
        
for (k ? k-- : 0, j = (rank[i] > 0? sa[rank[i] - 1] : 0; rank[i] > 0
                
&& r[i + k] == r[j + k]; k++)
            ;
}


int main() {
    
int m, t, i, j, sp, sb, se, mid, s, l, ans, c, w, ll;
    
char str[210];
    
bool visit[4010], isfind;
    
while (scanf("%d"&m), m) {
        sp 
= 27;
        
for (j = n = 0; j < m; j++{
            scanf(
"%s", str);
            
for (i = 0; str[i]; i++{
                r[n
++= str[i] - 'a';
            }

            r[n
++= sp++;
        }

        ll 
= strlen(str);
        da(r, sa, n, sp), calheight(r);
        
for (sb = 1, se = ll, mid = (sb + se) >> 1, s = 0, ans = -1; sb < se;) {
            isfind 
= false;
            
for (int i = 0; (i < n) && !isfind; i++{
                
if (height[i] < mid)
                    memset(visit, 
falsesizeof(visit)), t = 0;
                
if (height[i] >= mid) {
                    
if (t == 0{
                        l 
= sa[i - 1/ (ll + 1);
                        
if (!visit[l])
                            visit[l] 
= true, t++;
                    }

                    l 
= sa[i] / (ll + 1);
                    
if (!visit[l])
                        visit[l] 
= true, t++;
                    
if (t == m)
                        isfind 
= true, ans = i;
                }

            }

            
if (isfind && mid == se)
                
break;
            
if (isfind)
                (sb 
== mid && se > sb) ? (mid = se) : (sb = mid);
            
else
                se 
= mid - 1, mid = (se + sb) >> 1;
        }

        
if (ans != -1{
            
for (int i = 0; i < mid; i++{
                c 
= r[sa[ans] + i];
                putchar(c 
+ 'a');
            }

            puts(
"");
        }
 else
            puts(
"IDENTITY LOST");
    }

    
return 0;
}

   Suffix Array (DC3)
/*
 * Problem: 3450  User: Uriel 
 * Memory: 4084K  Time: 1110MS 
 * Language: C++  Result: Accepted 
 
*/

#include
<stdio.h>
#include
<stdlib.h>
#include
<string.h>
#define N 1000000
#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
int n, r[N * 3], sa[N * 3]; //注意数组大小
int wa[N], wb[N], wv[N], ws[N];

int c0(int *r, int a, int b) {
    
return r[a] == r[b] && r[a + 1== r[b + 1&& r[a + 2== r[b + 2];
}

int c12(int k, int *r, int a, int b) {
    
if (k == 2)
        
return r[a] < r[b] || r[a] == r[b] && c12(1, r, a + 1, b + 1);
    
else
        
return r[a] < r[b] || r[a] == r[b] && wv[a + 1< wv[b + 1];
}

void sort(int *r, int *a, int *b, int n, int m) {
    
int i;
    
for (i = 0; i < n; ++i)
        wv[i] 
= r[a[i]];
    
for (i = 0; i < m; ++i)
        ws[i] 
= 0;
    
for (i = 0; i < n; ++i)
        
++ws[wv[i]];
    
for (i = 1; i < m; ++i)
        ws[i] 
+= ws[i - 1];
    
for (i = n - 1; i >= 0--i)
        b[
--ws[wv[i]]] = a[i];
    
return;
}

void dc3(int *r, int *sa, int n, int m) {
    
int i, j, *rn = r + n, *san = sa + n, ta = 0, tb = (n + 1/ 3, tbc = 0, p;
    r[n] 
= r[n + 1= 0;
    
for (i = 0; i < n; ++i)
        
if (i % 3)
            wa[tbc
++= i;
    sort(r 
+ 2, wa, wb, tbc, m);
    sort(r 
+ 1, wb, wa, tbc, m);
    sort(r, wa, wb, tbc, m);
    
for (p = 1, rn[F(wb[0])] = 0, i = 1; i < tbc; ++i)
        rn[F(wb[i])] 
= c0(r, wb[i - 1], wb[i]) ? p - 1 : p++;
    
if (p < tbc)
        dc3(rn, san, tbc, p);
    
else
        
for (i = 0; i < tbc; ++i)
            san[rn[i]] 
= i;
    
for (i = 0; i < tbc; ++i)
        
if (san[i] < tb)
            wb[ta
++= san[i] * 3;
    
if (n % 3 == 1)
        wb[ta
++= n - 1;
    sort(r, wb, wa, ta, m);
    
for (i = 0; i < tbc; ++i)
        wv[wb[i] 
= G(san[i])] = i;
    
for (i = 0, j = 0, p = 0; i < ta && j < tbc; ++p)
        sa[p] 
= c12(wb[j] % 3, r, wa[i], wb[j]) ? wa[i++] : wb[j++];
    
for (; i < ta; ++p)
        sa[p] 
= wa[i++];
    
for (; j < tbc; ++p)
        sa[p] 
= wb[j++];
    
return;
}

int rank[N], height[N];
void calheight(int *r) {
    
int i, j, k;
    
for (i = 0; i < n; i++)
        rank[sa[i]] 
= i;
    
for (i = 0, height[0= k = 0; i < n; height[rank[i++]] = k)
        
for (k ? k-- : 0, j = (rank[i] > 0? sa[rank[i] - 1] : 0; rank[i] > 0
                
&& r[i + k] == r[j + k]; k++)
            ;
}


int main() {
    
int m, t, i, j, sp, sb, se, mid, s, l, ans, c, w, ll;
    
char str[210];
    
bool visit[4010], isfind;
    
while (scanf("%d"&m), m) {
        sp 
= 27;
        
for (j = n = 0; j < m; j++{
            scanf(
"%s", str);
            
for (i = 0; str[i]; i++{
                r[n
++= str[i] - 'a';
            }

            r[n
++= sp++;
        }

        ll 
= strlen(str);
        dc3(r, sa, n, sp), calheight(r);
        
for (sb = 1, se = ll, mid = (sb + se) >> 1, s = 0, ans = -1; sb < se;) {
            isfind 
= false;
            
for (int i = 0; (i < n) && !isfind; i++{
                
if (height[i] < mid)
                    memset(visit, 
falsesizeof(visit)), t = 0;
                
if (height[i] >= mid) {
                    
if (t == 0{
                        l 
= sa[i - 1/ (ll + 1);
                        
if (!visit[l])
                            visit[l] 
= true, t++;
                    }

                    l 
= sa[i] / (ll + 1);
                    
if (!visit[l])
                        visit[l] 
= true, t++;
                    
if (t == m)
                        isfind 
= true, ans = i;
                }

            }

            
if (isfind && mid == se)
                
break;
            
if (isfind)
                (sb 
== mid && se > sb) ? (mid = se) : (sb = mid);
            
else
                se 
= mid - 1, mid = (se + sb) >> 1;
        }

        
if (ans != -1{
            
for (int i = 0; i < mid; i++{
                c 
= r[sa[ans] + i];
                putchar(c 
+ 'a');
            }

            puts(
"");
        }
 else
            puts(
"IDENTITY LOST");
    }

    
return 0;
}

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