CQUPT 集训队专题训练（字符串）

字符串

A - 最小表示法 POJ - 1509
题意：

给出一个字符串首尾相连构成循环，求出以某哪个字母为起点，这个字符串的字典序最小

解题思路：

最小表示法维护两个指针，i=0（表示以此字母为起点时字典序最小）,j=1(用来维护i指针，与i指向的字母进行比较),当S[i]>S[j]时，i=j,j=j+1;当S[i]<S[j],j++,当S[i]==S[j],设一个k指针，i,j一直向下比较，直到不想等 。如果S[i+k] > S[j+k] i=i+k，否则j++，返回i和j的小者

代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <map>
#include <string>
#include <vector>
#include <queue>
using namespace std;
char ss[10024];
int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%s",ss);
        int len=strlen(ss);
        int i=0,j=1,k=0;
        while(i<len&&j<len&&k<len)
        {
            int t=ss[(i+k)%len]-ss[(j+k)%len];
            if(!t)
            k++;
            else
            {
                t>0?i=i+k+1:j=j+k+1;
                if(i==j)
                j++;
                k=0;
            }
        }
        if(i<j)
        cout<<i+1<<endl;
        else
        cout<<j+1<<endl;
    }
    return 0;
}
B - KMP HDU - 1686 
题意：

给出一个字符串W和一个字符串T，在T中有多少个W？

解题思路：

KMP，主要是那个nxt[i]辅助数组，表示看了几遍还是有点绕

[http://www.ituring.com.cn/article/59881][1]
代码：

include

include

include

include

include

include

include

using namespace std;
int lenw,lent;
char w[100010],t[1000010];
int nxt[1000010];

void getnext()
{
nxt[0]=-1;
int j=1,i;
for(;j {
i=nxt[j-1];
while(w[i+1]!=w[j]&&i>=0) i=nxt[i];
if(w[i+1]==w[j]) nxt[j]=i+1;
else
nxt[j]=-1;
}
}
int kmp()
{
int j=0,i=-1;
int count=0;
for(;j {
while(w[i+1]!=t[j]&&i>=0) i=nxt[i];
if(w[i+1]==t[j]) i++;
if(i==lenw-1)
{
count++;
i=nxt[i];
}
}
return count;
}
int main()
{
int n;
int len,ans;
scanf("%d",&n);
while(n--)
{
scanf("%s%s",w,t);
lenw=strlen(w);
lent=strlen(t);
getnext();
ans=kmp();
printf("%d\n",ans);
}
return 0;
}
```
D - 字典树 HDU - 1251
题意：

输入数据的第一部分是一张单词表,统计出以某个字符串为前缀的单词数量。

解题思路：

第一种思路是用到stl里面的map，直接统计单词表中所有子串为前缀的数量，代码简单但是时间复杂度比较高，第二种就是直接建立一棵字典树，将字符串向下延伸，沿途的权值加一。

代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <map>
#include <string>
#include <vector>
#include <queue>
#include <malloc.h>
#define maxn 26
using namespace std;
char str[15];
map<string,int> mp;
int main()
{
    while(gets(str)&&str[0]!='\0'){
        int len=strlen(str);
        for(int i=len-1;i>=0;i--)
        {
            mp[str]++;
            str[i]='\0';
        }
    }
    while(gets(str))
    {
        cout<<mp[str]<<endl;
    }
    return 0;
}
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int g[2000000][26]={0},tot;
int rak[1000000]={0};
char c='a';
void init()
{
    memset(g[1],0,sizeof(g[1]));
    tot=1;
}
void insert(char* s)
{
    int i;
    for(i=1;*s;++s)
    {
        if(!g[i][*s-c])
        {
            i=g[i][*s-c]=++tot;
            rak[i]++;
            memset(g[tot],0,sizeof(g[tot]));
        }else
        {
            i=g[i][*s-c];
            rak[i]++;
        }
    }
}
int query(char* s)
{
    int i;
    for(i=1;*s;++s)
    {
        if(!g[i][*s-c])return 0;
        i=g[i][*s-c];
    }
    return rak[i];
}
int main()
{
    char str[20];
    init();
    while(gets(str),strlen(str)>0)
    {
        insert(str);
    }
    while(scanf("%s",str)!=EOF)
    {
        printf("%d\n",query(str));
    }
    return 0;
}

E - Manacher POJ - 3974
题意：

给出一串字符串，字符串的长度不长于1000000 ，求出最长的回文子串。

解题思路：

先对字符串进行一次性处理，将两个字符之间加上#，使得奇回文串和偶回文串统一在一起考虑，辅助数组P［id］记录的是以字符str［id］为中心的最长回文串，当以str［id］为第一个字符，这个最长回文串向右延伸了P［id］个字符。

http://blog.csdn.net/ggggiqnypgjg/article/details/6645824/

代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <map>
#include <string>
#include <vector>
#include <queue>
using namespace std;
int len,cas;
char ss[1000010],s1[3000010]; 
int p[3000010];
void solve()
{
    int mx=0;
    int id,ans=1;
    for(int i=1;i<=len;i++)
    {
        if(mx>i)
        p[i]=min(p[2*id-i],mx-i);
        else
        p[i]=1;
        for(;s1[i+p[i]]==s1[i-p[i]];p[i]++);
        if(i+p[i]>mx)
        {
            mx=p[i]+i;
            id=i;
        }
        ans=max(ans,p[i]);
    }
    printf("Case %d: %d\n",cas++,ans-1);
 } 
int main()
{
    cas=1;
    while(scanf("%s",ss)!=-1)
    {
        if(strcmp(ss,"END")==0)
        break;
        len=strlen(ss);
        s1[0]='@';
        s1[1]='#';
        int i;
        for(i=0;i<len;i++)
        {
            s1[2*i+2]=ss[i];
            s1[2*i+3]='#';
        }
        len=2*i+3;
        solve();
    }
    return 0;
}