专题八(字符串)

题解

题目

A Glass Beads

题目大意：

    一个长度为N(N<=10000)字符串本身的首尾相接(最右边的字符右边连接最左边的字符)，问以哪一个字符为起点，能让这个字符串字典序最小。如果有多个起点，输出最左边的。
    T组数据。

解题思路：

    裸的最小表示法。
    小细节：把原字符串后面再接一个自己，处理的时候就不用取模了，在数据比较大的时候会快一点。
    时间复杂度o(T*N)，空间复杂度o(N)。

AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#define pq priority_queue
#define Pi acos(-1.0)
using namespace std;
#define MOD 1000000007
char s[20005];
int main()
{
    int t;
    int x,y,z,l;
    cin>>t;
    while(t--)
    {
        scanf("%s",s);
        l=strlen(s);
        for(int i=l;i<2*l;i++)
            s[i]=s[i-l];
        x=0;
        y=1;
        while(y<l && x<l)
        {
            z=0;
            while(z<l && s[x+z]==s[y+z]) z++;
            if(z==l)
                break;
            if(s[x+z]>s[y+z])
                x=x+z+1;
            else
                y=y+z+1;
            if(x==y)
                y++;
        }
        printf("%d\n",x+1);
    }
    return 0;
}

B Oulipo

题目大意：

    给出字符串W(1<=|W|<=10000)和T(1<=|T|<=1000000)，问T中有多少个W(可重叠)。
    T组数据。

解题思路：

    裸的kmp。
    找到第一个匹配后不退出，跑完整个T串，每次匹配长度为|W|的时候答案加一即可。
    时间复杂度o(T*(|W|+|T|))，空间复杂度o(|W|+|T|)。

AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#define pq priority_queue
#define Pi acos(-1.0)
using namespace std;
#define MOD 1000000007
char w[10005],t[1000005];
int nex[10005];
void pre_kmp(char nows[],int nownex[])
{
    nownex[0]=0;
    nownex[1]=0;
    int l=strlen(nows);
    for(int i=1;i<l;i++)
    {
        int j=nownex[i];
        while(j && nows[i]!=nows[j])
            j=nownex[j];
        if(nows[i]==nows[j])
            nownex[i+1]=j+1;
        else
            nownex[i+1]=0;
    }
}
int kmp(char nows1[],char nows2[],int nownex[])
{
    pre_kmp(nows1,nownex);
    int j=0,nowans=0;
    int l1=strlen(nows1),l2=strlen(nows2);
    for(int i=0;i<l2;i++)
    {
        while(j && nows1[j]!=nows2[i])
            j=nownex[j];
        if(nows1[j]==nows2[i])
            j++;
        if(j==l1)
        {
            nowans++;
            j=nownex[j];
        }
    }
    return nowans;
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        scanf("%s%s",w,t);
        printf("%d\n",kmp(w,t,nex));
    }
    return 0;
}

C Revolving Digits

题目大意：

    把正整数N(N<10^100000)看成一个首尾相接的字符串，根据起点的不同数字也会改变，例如104在不同起点时分别为410、041、104。问这些不同的数字中，比N本身大、小或者相等的数字各有多少个。起点不同但是数字相同只算一种。
    T(1<=T<=50)组数据。

AC代码：

    exkmp的应用。
    把原串作为模式串，把两个原串接在一起作为匹配串，然后当前起点开始的后缀如果和模式串的匹配长度等于模式串长，说明相等。如果小于，那么比较不同的这一位，就知道比N大还是比N小了。
    接下来解决重复的问题。以第一个点为起点的时候，匹配长度一定等于模式串长，后面如果再出现匹配长度等于模式串长，说明这个字符串有循环节，那么从这个起点开始后面的起点表示的数字都和前面是重复的，所以直接结束，就能实现去重。
    小细节：仔细看一下去重的方法会发现等于N的数字永远是1(滑稽)。
    时间复杂度o(T*lg(N))，空间复杂度o(lg(N))。

AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#define pq priority_queue
#define Pi acos(-1.0)
using namespace std;
#define MOD 1000000007
char s1[100005],s2[200005];
int nex[100005],exlen[200005];
int ans1,ans2;
void pre_exkmp(char nows[],int nownex[])
{
    int l=strlen(nows),x=0,p;
    nownex[0]=l;
    while(x<l && nows[x+1]==nows[x]) x++;
    nownex[1]=x;
    p=1;
    for(int i=2;i<l;i++)
    {
        if(nownex[i-p]+i<nownex[p]+p)
            nownex[i]=nownex[i-p];
        else
        {
            x=nownex[p]+p-i;
            if(x<0) x=0;
            while(x+i<l && nows[x]==nows[i+x]) x++;
            nownex[i]=x;
            p=i;
        }
    }
}
void exkmp(char nows1[],char nows2[],int nownex[],int nowex[])
{
    pre_exkmp(nows1,nex);
    int l1=strlen(nows1),l2=strlen(nows2),p,x;
    ans1=ans2=0;
    nowex[0]=l1;
    p=0;
    for(int i=1;;i++)
    {
        if(nownex[i-p]+i<nowex[p]+p)
            nowex[i]=nownex[i-p];
        else
        {
            x=nowex[p]+p-i;
            if(x<0) x=0;
            while(x+i<l2 && x<l1 && nows1[x]==nows2[i+x]) x++;
            nowex[i]=x;
            p=i;
        }
        if(nowex[i]==l1)
            break;
        else
        {
            if(nows2[i+nowex[i]]<nows1[nowex[i]])
                ans1++;
            else
                ans2++;
        }
    }
}
int main()
{
    int T;
    cin>>T;
    for(int t=1;t<=T;t++)
    {
        scanf("%s",s1);
        int nowl=strlen(s1);
        for(int i=0;i<2*nowl;i++)
            s2[i]=s1[i%nowl];
        s2[nowl*2]=0;
        exkmp(s1,s2,nex,exlen);
        printf("Case %d: %d 1 %d\n",t,ans1,ans2);
    }
    return 0;
}

D 统计难题

题目大意：

    给出一张单词表，然后针对每个询问的前缀求含有该前缀的单词有多少个，一个单词的前缀包含自己本身。单词长度不超过10。

解题思路：

    裸字典树。
    建一棵字典树，更新每个单词的时候把沿途的点的权值都加一。询问的时候找到对应的那个点返回他的权值就行了。
    小细节：注意下如果这个点不存在的情况，返回0。掌握一下内存池(伪)的概念和写法。
    时间复杂度o(总字符数)，空间复杂度o(26*总单词数)。

AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<malloc.h>
#define pq priority_queue
#define Pi acos(-1.0)
using namespace std;
#define MOD 1000000007
struct Node
{
    int num;
    int son[26];
}tre[1000005];
int nums=0;
char s[15];
void add(char nows[],int x)
{
    tre[x].num++;
    if(nows[0])
    {
        if(!tre[x].son[nows[0]-'a'])
            tre[x].son[nows[0]-'a']=++nums;
        add(nows+1,tre[x].son[nows[0]-'a']);
    }
}
int ask(char nows[],int x)
{
    if(nows[0])
    {
        if(!tre[x].son[nows[0]-'a'])
            return 0;
        else
            return ask(nows+1,tre[x].son[nows[0]-'a']);
    }
    else
        return tre[x].num;
}
int main()
{
    while(cin.getline(s,13),strlen(s))
        add(s,0);
    while(~scanf("%s",s))
        printf("%d\n",ask(s,0));
    return 0;
}

E Palindrome

题目大意：

    给一个字符串S(|S|<=1000000)，求它的最长回文子串的长度。
    多组数据。

解题思路：

    裸的manacher。
    时间复杂度o(|S|)，空间复杂度o(|S|)。

AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<malloc.h>
#define pq priority_queue
#define Pi acos(-1.0)
using namespace std;
#define MOD 1000000007
char s1[1000005],s2[2000005];
int len[2000005];
int mlc(char nows[],int nowlen[])
{
    int ans=0,mx=0,po,l=strlen(nows);
    for(int i=0;nows[i];i++)
    {
        if(mx>i)
            len[i]=min(mx-i+1,len[2*po-i]);
        else
            len[i]=1;
        while(i-len[i]>=0 && i+len[i]<l && nows[i-len[i]]==nows[i+len[i]])
            len[i]++;
        if(i+len[i]-1>mx)
        {
            mx=i+len[i]-1;
            po=i;
        }
        ans=max(ans,len[i]);
    }
    return ans-1;
}
int main()
{
    int l,t=0;
    while(scanf("%s",s1),s1[0]!='E')
    {
        t++;
        l=2*strlen(s1);
        for(int i=0;i<l;i++)
        {
            if(i%2)
                s2[i]=s1[i/2];
            else
                s2[i]='#';
        }
        s2[l]='#';
        s2[l+1]=0;
        printf("Case %d: %d\n",t,mlc(s2,len));
    }
    return 0;
}

F Safe Or Unsafe

题目大意：

    用0和1对一个字符串S中的字母编码，满足任意一个编码都不是另一个编码的前缀(保证无二义性)，然后将这个字符串编码，问这个字符串的最小编码长度会不会超过m(m是整数)。
    n组数据。

解题思路：

    题目都提示了哈夫曼编码，如果弄懂哈夫曼编码的概念这题应该是很简单的。
    扫描一遍字符串处理出每个字母出现的次数，然后把次数不为0的字母提取出来进行哈夫曼编码，最后把每个字母的哈夫曼编码长度乘上出现次数加起来和m进行比较。
    一个节点有两个属性，内含字符长度和当前编码长度。每次找到内含字符长度最小的两个点进行合并，合并后的点的内含字符长度等于两个点的内含字符长度相加，合并后的当前编码长度等于两个点当前编码长度加上两个点的内含字符长度。预处理每种字母的内含字符长度为出现次数，当前编码长度为0。
    小细节：特判一下只出现了一种字母的情况。代码很短我就不解释原理了，关于合并的操作大家自己模拟一下就明白了。
    时间复杂度o(|S|+26*log(26))，空间复杂度o(|S|)。

AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define pq priority_queue
#define Pi acos(-1.0)
using namespace std;
#define MOD 1000000007
struct Node
{
    int val,num;
    friend bool operator <(Node x1,Node x2)
    {
        return x1.num>x2.num;
    }
}temp,now;
int nums[30];
pq <Node> q;
char s[1000006];
int main()
{
    int t,k;
    cin>>t;
    while(t--)
    {
        memset(nums,0,sizeof(nums));
        scanf("%d",&k);
        scanf("%s",s);
        for(int i=0;s[i];i++)
            nums[s[i]-'a']++;
        for(int i=0;i<26;i++)
        {
            if(nums[i])
            {
                temp.val=0;
                temp.num=nums[i];
                q.push(temp);
            }
        }
        while(1)
        {
            temp=q.top();
            q.pop();
            if(q.empty())
                break;
            now=q.top();
            q.pop();
            temp.val+=temp.num+now.num+now.val;
            temp.num+=now.num;
            q.push(temp);
        }
        if(temp.num<=k && temp.val<=k)
            printf("yes\n");
        else
            printf("no\n");
    }
    return 0;
}