a tutorial on computer science

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  21 随笔 :: 0 文章 :: 17 评论 :: 0 Trackbacks
    给出一个长度为N的字符串,求出它的最小表示。
    算法是线性的,具体做法是设置两个指针fst,sec。fst代表当前找到的最小的字符串表示,sec表示下一个要匹配的初始位置。暴力的做法就是每次sec向后面移动一位o(N^2)的算法。线性的做法是根据前面的结果移动fst和sec。当我们比较fst和sec形成的字符串的时候,有三种情况。第一种是比较到了第fst+len-1位和sec+len-1位置,相等。那么我们发现,fst和sec相等,不用多说,fst要移动到sec位置,sec移动到sec+1位置。这个比较明显。然后是比较到第i位置的时候,str[fst+i] > str[ (sec + i )%len],我们可以看到sec现在比fst小了,那么fst = sec, sec++。这也比较明显。然后是str[fst+i] < str[ (sec + i )%len],这样,我们可以看到,以fst+k(k<i)的字符串和fst比,都比fst大,然后sec+i也比fst+i大,那么可知,sec到sec+i的那些玩意就不用再和fst比了,他们肯定比fst小。sec = sec+i+1。好了,其实是比较明显的一个算法,推一下就差不多了。第一次写错在了当相等的时候直接返回了,汗。写的还算干净。#include <cstdio>
#include <cstring>

const int maxn = 1001000;

char str[maxn];

int getans(int tlen)
{
  int len = tlen;
  int fst = 0,sec = 1,i;

  while(sec < len)
  {
    for(i=0;i<len;i++)
    {
      if(str[fst+i] != str[(sec+i)%len])
        break;
    }
    if(i == len)
    {
          fst = sec;
          sec = sec + 1;
    }
    else if(str[fst+i] < str[(sec+i)%len])
    {
       sec = sec + i + 1;
    }
    else if(str[fst+i] > str[(sec+i)%len])
     {
       fst = sec;
       sec = sec + 1;
     }
  }
  return fst;
}

int main()
{
  int tcase,tlen;
  scanf("%d",&tcase);
  while(tcase--)
  {
    scanf("%d%s",&tlen,str);
    int ans = getans(tlen);
    printf("%d\n",ans);
  }
  return 0;
}
posted on 2012-08-02 15:36 bigrabbit 阅读(839) 评论(0)  编辑 收藏 引用

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