2016寒假集训队第八次作业

题解

Probelm A:最小表示法

题意：给你个环形串，让你求出从何处断开得到的字符串的字典序最小。

题解：模版题。
思路：
(1).利用两个指针i，j。初始化时i指向s[0]，j指向s[1]。
(2).k=0开始，检验s[i+k]和s[j+k]是否相等，相等则k++，一直下去，直到找到第一个不相同的字符（若k试了一个字符串的长度也没找到不同，即整个串都是相同的字符。则那个位置就是最小表示位置，算法终止并返回）。该过程中s[i+k]和s[j+k]的关系有三种：

　　1).s[i+k]>s[j+k]，i滑动到i+k+1处，s[i-i+k-1]不会是循环字符串的"最小表示"的前缀。
　　2).s[i+k] 　　
　　3).s[i+k]==s[j+k]，则k++，if(k==len)返回结果。
　　若滑动后i==j，将正在变化的那个指针在+1.直到i，j把整个字符串都检验完毕，返回两者中小于len的值。
(3).返回min( i , j )

参考代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char str[10010];
int t,len,i,j,k;
int main()
{
    cin>>t;
    while (t--)
    {
        cin>>str;
        len=strlen(str);
        i=0;
        j=1;
        k=0;
        while (i<len && j<len && k<len)
        {
            if (str[(i+k)%len]==str[(j+k)%len]) k++;
            else
            {
                if (str[(i+k)%len]>str[(j+k)%len]) i=i+k+1;
                else j=j+k+1;
                if (i==j) j++;
                k=0;
            }
        }
        if (i<j) cout<<i+1<<endl;
        else cout<<j+1<<endl;
    }
    return 0;
}

Problem B:KMP

题意：两行分别为word和text，问你text中包含多少个word子串。

题解：模版题。。。mark一下学习网址。。
http://www.cppblog.com/oosky/archive/2006/07/06/9486.html

参考代码：

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
char str[10010],c[1000010];
int ans,str1[10010],t;
void getnext()
{
    int i=0,j=-1,len=strlen(str);
    str1[0]=-1;
    while (i<len)
    {
        if (j==-1 || str[i]==str[j])
        {
            i++;
            j++;
            if (str[i]==str[j]) str1[i]=str1[j];
            else str1[i]=j;
        }
        else j=str1[j];
    }
}
void getans()
{
    int i=0,j=0,lc=strlen(c),ls=strlen(str);
    while (j<lc)
    {
        if (str[i]==c[j])
        {
            i++;
            j++;
        }
        else
        {
            if (str1[i]==-1)
            {
                i=0;
                j++;
            }
            else i=str1[i];
        }
        if (i>=ls)
        {
            ans++;
            i=str1[ls];
        }
    }
}
int main()
{
    cin>>t;
    while (t--)
    {
        ans=0;
        cin>>str;
        cin>>c;
        getnext();
        getans();
        cout<<ans<<endl;
    }
    return 0;  
}

Problem D:字典树

题意：统计出以某个字符串为前缀的单词数量

题解：字典树不熟啊。。但是看题感觉map可以做就尝试了下。。运用map对单词表中所有单词中出现的前缀进行存储和记录，没出现一次，进行一次加加。

参考代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
struct node
{
    char name[20];
}a[1000010];
int ans[1000010];
char b[50],s;
int main()
{
    map<string,int>ans;
    int k=0,p=0;
    while(scanf("%c",&s))
    {
        if (s==10 && p==0) break;
        else
        if (s==10 && p>0)
        {
            p=0;
            k++;
        }
        else
        if (s!=10)
        {
            a[k].name[p]=s;
            ans[a[k].name]++;
            p++;
        }
    }
    while (cin>>b) printf("%d\n",ans[b]);
    return 0;
}

Problem E:Manacher

题意：求最长回文子串的长度。

题解：裸模版题。。mark一下学习网址。
https://segmentfault.com/a/1190000003914228

参考代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
char c[1000010],mark[2000010];
int p[2000010],len,j,d=1,maxlen,x,mx,l;
int manacher()
{
    len=strlen(c);
    mark[0]='$';
    mark[1]='#';
    l=2;
    for (int i=0; i<len; i++)
    {
        mark[l]=c[i];
        l++;
        mark[l]='#';
        l++;
    }
    maxlen=-1;
    mx=0;
    //cout<<mark<<endl;
    for (int i=1; i<l; i++)
    {
        if (i<mx) p[i]=min(p[2*x-i],mx-i);
        else p[i]=1;
        while (mark[i-p[i]]==mark[i+p[i]]) p[i]++;
        if (mx<i+p[i])
        {
            x=i;
            mx=i+p[i];
        }
        maxlen=max(maxlen,p[i]-1);
    }
    return maxlen;
}
int main()
{
    while(cin>>c)
    {
        if (strcmp(c,"END")==0) break;
        cout<<"Case "<<d++<<": "<<manacher()<<endl;
    }  
    return 0;  
}