标签存档：字符串

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1535

【算法分析】

这是一个好题。

我讲讲我的做法。

首先模板一定是整个串的前缀，同时也是整个串的后缀。

那么可以先利用KMP求出所有满足这一条件的位置。

在满足了这一条件以后，答案就满足单调性了。

为什么？反正尾巴是肯定可以匹配的。然后那么多了总比小的可行方案多。。。

哎，难以言表啊。

然后就是二分答案+KMP判定了。

如果KMP比较熟练的话，应该不成问题。

【时间复杂度】O(n lg n)

【空间复杂度】O(n)

【其它】

1Y。我只想说，常数才是王道。

虽然利用扩展KMP+双向链表可以在O(n)做出来，但是常数好像比较沙茶。。。

强力Orz oimaster！！！

1 10278 Matt 3368K 30MS Pascal 1.00K 2010-02-28 13:07:34 2 9414 Matt 3368K 60MS Pascal 1.21K 2010-02-12 22:51:48 3 13806 oimaster 2680K 76MS G++ 0.43K 2010-03-18 22:12:04 4 10277 Matt 3372K 76MS Pascal 1.00K 2010-02-28 13:07:07 5 15893 sos 3652K 91MS G++ 1.02K 2010-03-25 19:54:03 6 25970 luojiewei 11096K 107MS Pascal 0.85K 2010-05-26 14:47:59 7 31701 edward_mj 3524K 121MS G++ 0.82K 2010-06-20 11:37:53 8 16133 sos 4624K 137MS G++ 1.35K 2010-03-26 17:18:43 9 16136 sos 4624K 138MS G++ 1.38K 2010-03-26 17:26:48 10 14202 Sachs 11180K 153MS Pascal 1.56K 2010-03-20 15:36:15 11 29479 zxytim 12316K 153MS G++ 1.45K 2010-06-13 12:06:35 12 29475 hyf042 12516K 154MS G++ 1.54K 2010-06-13 12:04:10 13 13690 wu3412790 11180K 170MS Pascal 1.22K 2010-03-18 12:22:58 14 7421 tracyhenry 5344K 185MS Pascal 1.81K 2009-10-23 18:20:52 15 14204 Jason 11692K 186MS Pascal 1.02K 2010-03-20 15:37:19 16 11454 Jason 11696K 200MS Pascal 1.02K 2010-03-05 14:32:44 17 29484 sonicmisora 12324K 201MS G++ 1.13K 2010-06-13 12:09:57 18 5437 pyf 14712K 231MS Pascal 2.47K 2009-07-09 14:28:26 19 9559 curimit 12900K 246MS Pascal 1.58K 2010-02-17 18:22:06 20 16179 AekdyCoin 10888K 261MS Pascal 2.33K 2010-03-26 19:00:19

【CODE】

#include const int N=500005;
int n;
int next[N],L[N];
char S[N];

bool Can(int Limit){
     int i,j=next[Limit];
     for (i=Limit+1;i<=n;i++){
         while (j && S[j+1]!=S[i]) j=next[j];
         if (S[j+1]==S[i]) j++;
         if (!j) return false;
         if (j==Limit) j=next[j];
     }
}

int main(){
    int i,j,l,r,mid,tot;
    scanf("%s",S+1);
    n=strlen(S+1);
    next[1]=j=tot=0;
    for (i=2;i<=n;i++){
      while (j && S[j+1]!=S[i]) j=next[j];
      if (S[j+1]==S[i]) j++;
      next[i]=j;
    }
    for (i=n;i;i=next[i]) L[++tot]=i;
    l=1; r=tot;
    while (l          mid=(l+r+1)/2;
          if (Can(L[mid])) l=mid;
                      else r=mid-1;
    }
    printf("%dn",L[l]);
}

【题目大意】

给定两个串，让你求满足A[i..i+k]=B[j..j+k]且k>=K的(i,j)的数目。

【算法分析】

先把两个串连在一起，中间加一个特殊字符。

然后建立后缀数组和height数组。

最后对height进行线性分组，同组的height都>=K

然后注意到我们需要统计的是每一个点对(i,j)其中i为A串的后缀，j为B串的后缀，他们的lcp(i,j)-limit+1，然后加起来。但是我们注意到越向后延伸，对于同一个点的lcp只会单调递减，然后用一个栈合并lcp已经被并为同一个数字的区间，最后输出就可以。

【其它】3WA，s1和s2忘记搞成long long了。。。

表示紧紧跟随lcc的脚步。。。

【CODE】

#include

【题目大意】

求所有对于同一字符串的前缀和后缀相等的位置。

【算法分析】

KMP，然后一直从n一直next回去，路上的都是。

为什么呢？

首先从在n的第一次next是找最长的S[1,K]=S[n-K+1,n]

这个容易理解。

然后接下来的next是求最长的S[1,K]=S[J-K+1,J]

注意了，这个S[J-K+1,J]必然与S[n-K+1,n]相等。（可以用数学归纳法证明一下）

于是对应下一个前缀等于后缀的位置。

所以，这样一直下去就会找到所有的前缀等于后缀的位置。

【其它】1A

http://hi.baidu.com/aekdycoin/blog/item/fbe5a03233bd1648ad4b5f1c.html

紧紧跟随师傅的脚步。

【CODE】

#include #include #include

int next[500000],n,ans[500000],ansl;
char s[500000];

int main(){
    int i,j;
    while (scanf("%sn",&s[1])!=EOF){
          n=strlen(s+1);
          next[1]=0;
          j=0;
          for (i=2;i<=n;i++){
              while (j && s[j+1]!=s[i]) j=next[j];
              if (s[j+1]==s[i]) j++;
              next[i]=j;
          }
          ansl=1; ans[1]=n;
          j=n;
          while (1){
                if (next[j]==0) break;
                j=next[j];
                ans[++ansl]=j;
          }
          for (i=ansl;i>=1;i–){
              printf("%d",ans[i]);
              if (i!=1) printf(" ");
          }
          printf("n");
    }
}

【题目大意】

给一个串，让你求他最少由多少个可重叠的回文串所组成。输出ans-1（要拼接几次）

【算法分析】

令读入的串为s，s’为s翻转以后的字符串，然后再令S=s+’$’+s’。

对S建立后缀数组，height和lcp

然后枚举对称中心（注意，对称中心可能在字符上，也可能在字符之间,即回文串长度为偶数）

然后利用lcp求出最长覆盖区间。

然后问题变为用最少的区间去覆盖1~n这一段。

直接贪心：先将区间按L排序，然后枚举答案，看答案为ans时最多能覆盖到多远。

如果覆盖完整个1~n，那就可以输出了。

【其它】

TLE,WA了无限遍。。。

一个原因是因为一开始倍增算法里面用的C++的sort，后面改成基数排序就不超时了。

然后另一个原因是因为没有考虑到回文串为偶数长度时，对称轴不在字符上。

另外很不幸。。。我垫底了

果然大家用的都是DC3。。。只有我不会。。。

Submit Time Language Run Time(ms) Run Memory(KB) User Name 2010-02-21 17:03:31 C++ 70 1456 ConanKudo 2010-02-22 10:38:50 C++ 250 11148 lccycc 2010-02-21 19:42:45 C++ 400 20692 ILJ 2010-02-21 17:12:23 C++ 430 12416 zgmf_x20a 2010-02-22 17:53:00 C++ 510 21368 my icpc is going on,有要事先闪了 2010-02-22 17:56:12 C++ 510 21368 my icpc is going on,有要事先闪了 2010-02-22 17:50:59 C++ 520 22152 my icpc is going on,有要事先闪了 2010-02-22 17:48:57 C++ 540 26536 my icpc is going on,有要事先闪了 2010-02-22 18:22:56 C++ 550 23324 my icpc is going on,有要事先闪了 2010-02-22 18:21:04 C++ 600 23324 my icpc is going on,有要事先闪了 2010-02-22 22:52:08 C++ 720 13856 edward

【CODE】

#include #include #include #include #include using namespace std;
const int N=55555*2;
int n,e;
char S[N],lg[N];
int rank[N],sa[N],height[N],ls[N];
int lcp[N][18],TOT;
struct qj{int l,r;}d[N];
struct satmp{int a,b,pos;}a[N];
struct gtp{int next;satmp y;}g[N];

void init(){
    int i,j;
    n=strlen(S+1);
    S[n+1]=’$’;
    j=n+1;
    for (i=n;i>=1;i–){
        j++;
        S[j]=S[i];
    }
    n=j;
    lg[1]=0;
    for (int i=2;i<=n;i++)
      if (i==1<                      else lg[i]=lg[i-1];
}

void Jsort(){
    int i,t,tot;
    e=0; tot=0; memset(ls,0,sizeof(int)*(n+1));
    for (i=1;i<=n;i++){
        e++;
        g[e].y=a[i];
        g[e].next=ls[a[i].b];
        ls[a[i].b]=e;
    }
    for (i=1;i<=n;i++)
      for (t=ls[i];t;t=g[t].next)
        a[++tot]=g[t].y;
       
    e=0; tot=0; memset(ls,0,sizeof(int)*(n+1));
    for (i=n;i>=1;i–){
        e++;
        g[e].y=a[i];
        g[e].next=ls[a[i].a];
        ls[a[i].a]=e;
    }   
    for (i=1;i<=n;i++)
      for (t=ls[i];t;t=g[t].next)
        a[++tot]=g[t].y;
}   

inline bool cmp(satmp X,satmp Y){
    return X.a}

void GetRank(){
    int R=0;
    for (int i=1;i<=n;i++){
      if (!R || a[i].a!=a[i-1].a || a[i].b!=a[i-1].b) R++;
      rank[a[i].pos]=R;
    }   
}   
void build(){
    for (int i=1;i<=n;i++){a[i].a=S[i];a[i].b=0;a[i].pos=i;}
    sort(a+1,a+n+1,cmp);
    GetRank();
    for (int K=0;1<        int k=1<        for (int i=1;i<=n;i++){
            a[i].a=rank[i]; a[i].b=0;
            if (i+k<=n) a[i].b=rank[i+k];
            a[i].pos=i;
        }
        Jsort();
        GetRank();
    }
    for (int i=1;i<=n;i++) sa[rank[i]]=i;
}   

void makeheight(){
    height[1]=0;
    int i,j,k,st;
    for (i=1;i<=n;i++){
        if (rank[i]==1) continue;
        st=max(height[rank[i-1]]-1,0); j=i+st; k=sa[rank[i]-1]+st;
        while (j<=n && k<=n && S[j]==S[k]){j++;k++;st++;}
        height[rank[i]]=st;
    }
}

void initlcp(){
    for (int i=1;i<=n;i++) lcp[i][0]=height[i];
    for (int k=1;1<      for (int i=1;i+(1<        lcp[i][k]=min(lcp[i][k-1],lcp[i+(1<}

inline int Lcp(int l,int r){
    if (l>r) swap(l,r);
    l++;
    int k=lg[r-l+1];
    return min(lcp[l][k],lcp[r-(1<}   

void Ml(){
    int i,j=n+1,LCP;
    TOT=0;
    for (i=1;i<=n/2;i++){
        j–;
        LCP=Lcp(rank[i],rank[j]);
        TOT++;
        d[TOT].l=i-LCP+1;
        d[TOT].r=i+LCP-1;
    }
    j=n+1;   
    for (int i=1;i        j–;
        LCP=Lcp(rank[i+1],rank[j]);
        TOT++;
        d[TOT].l=i-LCP+1;
        d[TOT].r=i+LCP;
    }   
    n/=2;
}   

inline bool TXcmp(qj X,qj Y){
    return X.l}   

void TanXin(){
    sort(d+1,d+1+TOT,TXcmp);
    int now=0,ans,i=0,expand;
    for (ans=1;;ans++){
        expand=0;
        while (i<=TOT && d[i+1].l<=now+1){
            i++;
            if (d[i].r>expand) expand=d[i].r;
        }
        now=expand;
        if (now>=n){
            printf("%dn",ans-1);
            return;
        }   
    }   
}   

int main(){
    while (scanf("%s",S+1)!=EOF){
        init();
        build();
        makeheight();
        initlcp();
        Ml();
        TanXin();
        memset(S,0,sizeof(S));
    }   
}   

【题目大意】

给一个串A，一个串B，然后在B串中，从A串的某个位置开始匹配，然后匹配到A串末尾又匹配回A串开头，然后问最长的匹配段是多少?

如果A串在B串中没有一个正常的从1开始的匹配的话，输出bad。

【算法分析】

当时没想到，经lcc教导，终于明白了。。。ORZ！

先KMP。

我是开了一个邻接表，记录连续的完全匹配。

然后给每一个连续的完全匹配向前和向后延伸。然后去更新ans即可。

【CODE】

#include #include struct gtp{int y,next;}g[1001111];
int m,n,e;
int next[1111];
int P[1111],T[1001111];
int tot;
int belong[1001111],ls[1001111];

void makenext(){
    next[1]=0;
    int i,j=0;
    for (i=2;i<=m;i++){
        while (j>0 && P[j+1]!=P[i]) j=next[j];
        if (P[j+1]==P[i]) j++;
        next[i]=j;
    }   
}   

inline void addedge(int &x,int &y){
    e++;
    g[e].y=y; g[e].next=ls[x]; ls[x]=e;
}   

void kmp(){
    for (int i=1;i<=n;i++){
        belong[i]=0;
        ls[i]=0;
    }   
    tot=0;
    e=0;
    int i,j=0;
    for (i=1;i<=n;i++){
        while (j>0 && P[j+1]!=T[i]) j=next[j];
        if (P[j+1]==T[i]) j++;
        if (j==m){
            if (!belong[i-m]){
                tot++;
                belong[i]=tot;
            }
            else belong[i]=belong[i-m];
            addedge(belong[i],i);
            j=next[j];
        }   
    }   
}

void solve(){
    if (tot==0){
        printf("badn");
        return;
    }   
    int i,j,k,t,now,ans=0,num,st;
    for (i=1;i<=tot;i++){
        j=g[ls[i]].y+1;
        k=1;
        while (j<=n && k<=m && P[k]==T[j]){j++; k++;}
        j–; k–;
        now=k; num=0;
        for (t=ls[i];t;t=g[t].next){num++;st=g[t].y-m;}
        now+=m*num;
        j=st; k=m;
        while (j>=1 && k>=1 && P[k]==T[j]){j–; k–;}
        now+=m-k;
        if (now>ans) ans=now;
    }   
    printf("%dn",ans);
}   

int main(){
    for (;;){
        if (scanf("%d%d",&m,&n)==EOF) break;
        for (int i=1;i<=m;i++) scanf("%d",&P[i]);
        for (int i=1;i<=n;i++) scanf("%d",&T[i]);
        makenext();
        kmp();
        solve();
    }   
}