当前位置： 移动技术网 > IT编程>开发语言>C/C++ > 第三周训练总结

第三周训练总结

2019年09月13日  | 移动技术网IT编程  | 我要评论

战龙四驱游戏,薇拉火语,王李丹妮全婐毛

一、kmp+最大最小值表示法

最大最小值表示法

最大最小表示法用于解决字符串的同构问题，其在复杂度为$ o(n) $的时间内求出一个字符串的所有同构串中字典序最大（小）的串的起始位置。

应用：

  • 给出$ n $个循环字符串判断有多少不同字符串：逐个用最大（小）表示法表示，然后加入 \(set\) 去重
  • 循环字符串所有同构串中字典序最大（小）的表示：用最大（小）表示法求出起始位置，输出即可
  • 判断两个字符串是否同构：将两字符串用最大（小）表示法表示，然后逐个字符比较

原理：

设一字符串 \(s\)，且 $s’ \(是\) s $的循环同构的串的最小表示，那么对于字符串循环同构的最小表示法，其问题实质是求 s 串的一个位置，从这个位置开始循环输出 \(s\)，得到的 $s’ $字典序最小。

最朴素的算法是设$ i\(、\)j \(两个指针，\)i \(指向最小表示的位置，\)j $作为比较指针。

令 \(i=0\)，\(j=1\)，那么：

  • 若 \(s[i]>s[j]\)，则：\(i=j\)，\(j=i+1\)
  • 若 \(s[i]<s[j]\)，则：\(j++\)
  • 若 \(s[i]=s[j]\)，则设指针 \(k\)，分别从 $i $和 $j \(位置向下比较，直到\) s[i]!=s[j]$
  • 若 \(s[i+k]>s[j+k]\)，则：\(i=j\)，\(j=i+1\)
  • 否则$ j++$

最后返回 $i $即可

可以看出，朴素算法在 $s[i]=s[j] \(时，\)i $的指针移动的太少了，在遇到像 $bbb…bbbbbba $这样复杂的字符串时，时间复杂度可能会退化到 \(o(n^2)\)，针对这一问题加以改进可得到 \(o(n)\) 的最小表示法的算法，其核心思路是在$ s[i]=s[j]$ 时同时维护 \(i\)、$j $两个指针

同样令 \(i=0\)，\(j=1\)，那么：

  • 若 \(s[i]>s[j]\)，则：\(i=j\)，\(j=i+1\)
  • 若 \(s[i]<s[j]\)，则：\(j++\)
  • 若$ s[i]=s[j]\(，则设指针\) k\(，分别从\) i \(和\) j $位置向下比较，直到 \(s[i]!=s[j]\)
  • 若 \(s[i+k]>s[j+k]\)，则：\(i=i+k\)
  • 否则 \(j++\)

最后返回$ i $和 $j $的小者即可

1、最小值表示法

int minmumrepresentation(char *str) //最小表示法
{
    int len=strlen(str);
    int i=0;                        //指向字符串最小的位置
    int j=1;                        //比较指针
    int k=0;            //str[i]与str[j]相等时一次移动几个
    while(i<len&&j<len&&k<len)
    {
        int temp=str[(i+k)%len]-str[(j+k)%len];//比较值的长度
        if(temp==0)
            k++;
        else
        {
            if(temp>0)              //维护i
                i=i+k+1;
            else                    //维护j
                j=j+k+1;
            if(i==j)                //相等时比较指针后移
                j++;
            k=0;
        }
    }
    return i<j?i:j;                 //返回i、j中较小的那个
}

2、最大值表示法

int maxmumrepresentation(char *str) //最大表示法
{
    int len=strlen(str);
    int i=0;                        //指向字符串最小的位置
    int j=1;                        //比较指针
    int k=0;            //str[i]与str[j]相等时一次移动几个
    while(i<len&&j<len&&k<len)
    {
        int temp=str[(i+k)%len]-str[(j+k)%len];//比较值的长度
        if(temp==0)
            k++;
        else
        {
            if(temp>0)              //维护i
                j=j+k+1;
            else                    //维护j
                i=i+k+1;
            if(i==j)                //相等时比较指针后移
                j++;
            k=0;
        }
    }
    return i<j?i:j;                 //返回两者最小值
}

hdu-3374解题思路

首先判定是否是循环串，然后用最小表示法和最大表示法来找出对应的位置，最小表示法可以找出比如一个环形的字符串，找出某个字符开始，然后这个字符串字典序最小

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#define pi acos(-1.0)
#define e 1e-9
#define inf 0x3f3f3f3f
#define ll long long
const int mod=10007;
const int n=1000000+5;
const int dx[]= {-1,1,0,0};
const int dy[]= {0,0,-1,1};
using namespace std;
int next[n];
char str[n];
void getnext(char p[])
{
    next[0]=-1;
    int len=strlen(p);
    int j=0;
    int k=-1;

    while(j<len)
    {
        if(k==-1||p[j]==p[k])
        {
            k++;
            j++;
            next[j]=k;
        }
        else
        {
            k=next[k];
        }
    }
}
int minmumrepresentation(char *str) //最小表示法
{
    int len=strlen(str);
    int i=0;
    int j=1;
    int k=0;
    while(i<len&&j<len&&k<len)
    {
        int temp=str[(i+k)%len]-str[(j+k)%len];
        if(temp==0)
            k++;
        else
        {
            if(temp>0)
                i=i+k+1;
            else
                j=j+k+1;
            if(i==j)
                j++;
            k=0;
        }
    }
    return i<j?i:j;
}
int maxmumrepresentation(char *str) //最大表示法
{
    int len=strlen(str);
    int i=0;
    int j=1;
    int k=0;
    while(i<len&&j<len&&k<len)
    {
        int temp=str[(i+k)%len]-str[(j+k)%len];
        if(temp==0)
            k++;
        else
        {
            if(temp>0)
                j=j+k+1;
            else
                i=i+k+1;
            if(i==j)
                j++;
            k=0;
        }
    }
    return i<j?i:j;
}


int main()
{
    while(scanf("%s",str)!=eof)
    {
        getnext(str);

        int n=strlen(str);
        int len=n-next[n];

        int num=1;//数量
        if(n%len==0)
            num=n/len;

        int minn=minmumrepresentation(str);//最小表示
        int maxx=maxmumrepresentation(str);//最大表示

        printf("%d %d %d %d\n",minn+1,num,maxx+1,num);
    }
    return 0;
}

二、

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网