**ZROI 8.19 D班作业题** - 博客

ZROI 8.19 D班作业题

Problem D-Censoring

Farmer John has purchased a subscription to Good Hooveskeeping magazine for his cows, so they have plenty of material to read while waiting around in the barn during milking sessions. Unfortunately, the latest issue contains a rather inappropriate article on how to cook the perfect steak, which FJ would rather his cows not see (clearly, the magazine is in need of better editorial oversight).
FJ has taken all of the text from the magazine to create the string S of length at most 10^6 characters. From this, he would like to remove occurrences of a substring T to censor the inappropriate content. To do this, Farmer John finds the _first_ occurrence of T in S and deletes it. He then repeats the process again, deleting the first occurrence of T again, continuing until there are no more occurrences of T in S. Note that the deletion of one occurrence might create a new occurrence of T that didn't exist before.
Please help FJ determine the final contents of S after censoring is complete
有一个S串和一个T串，长度均小于1,000,000，设当前串为U串，然后从前往后枚举S串一个字符一个字符往U串里添加，若U串后缀为T，则去掉这个后缀继续流程。

Input
The first line will contain S. The second line will contain T. The length of T will be at most that of S, and all characters of S and T will be lower-case alphabet characters (in the range a..z).

Output
The string S after all deletions are complete. It is guaranteed that S will not become empty during the deletion process.

Sample Input
whatthemomooofun
moo

Sample Output
whatthefun
Hint

KMP+栈，双管齐下。
先导出KMP的NEXT数组，再每次用栈记录
std:

#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
char a[N],b[N];
int n,m;
int l=0;
int kmp[N];
char s[N];
int w[N];
int t;
int main()
{
    scanf("%s%s",a+1,b+1);
    n=strlen(a+1);
    m=strlen(b+1);
    for(int i=2;i<=m;i++)
    {
        while(l&&b[l+1]!=b[i]) l=kmp[l];
        if(b[l+1]==b[i]) l++;
        kmp[i]=l;
    }
    for(int i=1;i<=n;i++)
    {
        int l=w[t];
        s[++t]=a[i];
        while(l&&b[l+1]!=a[i]) l=kmp[l];
        if(b[l+1]==a[i]) l++;
        if(l==m) t-=m;
        else w[t]=l;
    }
    s[t+1]='\0';
    puts(s+1);
    return 0;
}

Problem C-Count the string

It is well known that AekdyCoin is good at string problems as well as number theory problems. When given a string s, we can write down all the non-empty prefixes of this string. For example:
s: "abab"
The prefixes are: "a", "ab", "aba", "abab" For each prefix, we can count the times it matches in s. So we can see that prefix "a" matches twice, "ab" matches twice too, "aba" matches once, and "abab" matches once. Now you are asked to calculate the sum of the match times for all the prefixes. For"abab", it is 2 + 2 + 1 + 1 = 6. The answer may be very large, so output the answer mod 10007.
Input
The first line is a single integerT,indicating the number of test cases. For each case, the first line is an integer n (1 <= n <= 200000), which is the length of string s. A line follows giving the string s. The characters in the strings are all lower-case letters.
Output For each case, output only one number: the sum of the match times for all the prefixes of s mod 10007.

Sample Input
1
4
abab

Sample Output
6

f[i]表示以i结尾的最大匹配数若a[i]==a[j]或j==0 f[i]=f[j]+1
否则 j=kmp[j]
std:

#include<bits/stdc++.h>
using namespace std;
const int N=200005;
#define mod 10007;
int t;
int n;
char s[N];
int f[N];
int kmp[N];
int ans;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        ans=0;
        memset(f,0,sizeof(f));
        scanf("%d",&n);
        scanf("%s",s+1);
        kmp[1]=0;
        int i=1,j=0;
        while(i<=n)
        {
            if(j==0||s[i]==s[j])
            {
                f[i]=(f[j]+1)%mod; 
                i++;
                j++;
                if(s[i]==s[j])
                    kmp[i]=kmp[j];
                else
                    kmp[i]=j;
            }
            else
            {
                j=kmp[j];
            }
        }
        for(int i=1;i<=n;i++)
        {
            ans+=f[i];
            ans%=mod;
        }
        printf("%d\n",ans);
    }
    return 0;
}

Problem E-字符串大师

一个串T是S的循环节，当且仅当存在正整数k，使得S是T^k(即T重复k次)的前缀，比如abcd是abcdabcdab的循环节。给定一个长度为n的仅由小写字符构成的字符串S，请对于每个k(1<=k<=n)，求出S长度为k的前缀的最短循环节的长度per_i。字符串大师小Q觉得这个问题过于简单，于是花了一分钟将其AC了，他想检验你是否也是字符串大师。
小Q告诉你n以及per_1,per_2,...,per_n，请找到一个长度为n的小写字符串S，使得S能对应上per。
Input
第一行包含一个正整数n(1<=n<=100000)，表示字符串的长度。
第二行包含n个正整数per_1,per_2,...per_n(1<=per_i<=i)，表示每个前缀的最短循环节长度。输入数据保证至少存在一组可行解。
Output 输出一行一个长度为n的小写字符串S，即某个满足条件的S。
若有多个可行的S，输出字典序最小的那一个。

Sample Input
5
1 2 2 2 5

Sample Output
ababb

Hint

先推出kmp数组，再按位做
std:

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int n; 
int pre[N],kmp[N];
char s[N];
bool u[28];
int main()
{
    while(~scanf("%d",&n))
    {
        kmp[0]=-1;
        for(int i=0;i<n;i++) scanf("%d",&pre[i]);
        for(int i=0;i<n;i++) kmp[i+1]=i+1-pre[i];
        memset(u,0,sizeof(u));
        s[0]='a';
        for(int i=2;i<=n;i++)
        {
            memset(u,0,sizeof(u));
            if(kmp[i]!=0)
                s[i-1]=s[kmp[i]-1];
            else
            {
                u[0]=1;
                int sum=kmp[i-1];
                while(sum)
                {
                    u[s[sum]-'a']=1;
                    sum=kmp[sum];
                }
                for(int j=0;j<26;j++)
                {
                    if(u[j]==0)
                    {
                        s[i-1]=j+'a';
                        break;
                    }
                }
            }
        }
        s[n]=0;
        printf("%s\n",s);
    }
    return 0; 
}

QYJ的博客

博客

ZROI 8.19 D班作业题

评论