2020-08-01

http://icpc.upc.edu.cn/problem.php?cid=1459&pid=4

题目描述

Three friends like to play the following game. The first friend chooses a string S. Then the second friend constructs a new string T that consists of two copies of the string S. finally, the third friend inserts one letter at the beginning, the end or somewhere inside the string T, thereby creating a string U. You are given the string U and your task is to reconstruct the original string S.

输入

The first line of the input contains N（2 ≤ N ≤ 2000001）, the length of the final string U. The string U itself is given on the second line. It consists of N uppercase English letters (A, B, C, . . . , Z).

输出

Your program should print the original string S. However, there are two exceptions: 1.If the final string U could not have been created using the above procedure, you should print NOT POSSIBLE. 2.If the original string S is not unique, you should print NOT UNIQUE.

样例输入

7
ABXCABC

样例输出

ABC

解析

字符串哈希的应用，比较去除一个字母后前半部分的哈希值和后半部分哈希值是否相同

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=2e6+500;
char a[N]="";
int base=131;
ull p[N]={0};
ull h[N]={0};
ull get(ull l,ull r)
{
    return h[r]-h[l-1]*p[r-l+1];
}
int main()
{
    int n;
    scanf("%d",&n);
    if(n%2==0)
    {
        printf("NOT POSSIBLE\n");
        return 0;
    }
    scanf("%s",a+1);
    p[0]=1;
    for(int i=1;i<=n;i++)
        p[i]=p[i-1]*base;
    for(int i=1;i<=n;i++)
        h[i]=h[i-1]*base+a[i]-'A';
    ull flag=0,ans,pos;    ///注意用ull，ans数据比较大
    for(int i=1;i<=n;i++)
    {
        ull s1,s2;
        if(i<=n/2)
        {
            s1=h[i-1]*p[n/2-i+1]+get(i+1,n/2+1);
        }
        else
        {
            s1=h[n/2];
        }
        if(i<=n/2+1)
        {
            s2=get(n-n/2+1,n);
        }
        else
        {
            s2=get(n/2+1,i-1)*p[n-i]+get(i+1,n);
        }
        if(s1==s2)
        {
            if(flag&&ans!=s1)
            {
                printf("NOT UNIQUE\n");
                return 0;
            }
            ans=s1;
            pos=i;
            flag=1;
        }
    }
    if(flag)
    {
        for(int i=1,j=0;j<n/2;i++)
        {
            if(i==pos)
                continue;
            else
                printf("%c",a[i]),j++;
        }
        printf("\n");
    }
    else
    {
        printf("NOT POSSIBLE\n");
    }
}

http://icpc.upc.edu.cn/problem.php?cid=1459&pid=10

题目描述

一块花布条，里面有些图案，另有一块直接可用的小饰条，里面也有一些图案。对于给定的花布条和小饰条，计算一下能从花布条中尽可能剪出几块小饰条来呢？

输入

输入中含有一些数据，分别是成对出现的花布条和小饰条，其布条都是用可见ASCII字符表示的，可见的ASCII字符有多少个，布条的花纹也有多少种花样。花纹条和小饰条不会超过1000个字符长。如果遇见#字符，则不再进行工作。

输出

输出能从花纹布中剪出的最多小饰条个数，如果一块都没有，那就老老实实输出0，每个结果之间应换行。

样例输入

abcde a3
aaaaaa  aa
#

样例输出

0
3

解析

kmp模板题目，匹配相同的字符串

#include<bits/stdc++.h>
using namespace std;
char a[2005]={0};
char str[2005]={0};
int Next[2005]={0};
int getNext()
{
    int i=0,j=-1;
    Next[0]=-1;
    while(a[i])
    {
        if(j==-1||a[i]==a[j])
        {
            i++;
            j++;
            Next[i]=j;
        }
        else
        {
            j=Next[j];
        }
    }
}
int main()
{
    while(1)
    {
        scanf("%s",str);
        if(str[0]=='#')
            break;
        memset(Next,0,sizeof(Next));
        scanf("%s",a);
        getNext();
        int lena=strlen(a),lens=strlen(str);
        int j=0,sum=0,i=0;
        while(i<=lens)
        {
            if(j==-1||str[i]==a[j])
            {
                i++;
                j++;
            }
            else
            {
                j=Next[j];
            }
            if(j==lena)
            {
                sum++;
                j=0;
            }
        }
        printf("%d\n",sum);
    }
}