2020-7-31

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

题目

这是一道模板题。
给定一个字符串A和一个字符串B，求B在A中的出现次数。A和B中的字符均为英语大写字母或小写字母。
A中不同位置出现的B可重叠。

输入

输入共两行，分别是字符串A和字符串B。

输出

输出一个整数，表示B在A中的出现次数。

样例输入

zyzyzyz
zyz

样例输出

3

提示

1≤A,B的长度≤10^6，A、B仅包含大小写字母。

解析

这是一道字符串哈希的题目

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include 
using namespace std;
typedef long long ll;
const int N=1e6+500;
char a[N]="";
char b[N]="";
int base=31;
long long p[N]={0};
long long h[N]={0};
long long sum1=0,js1,sum=0;
int la=1,lb=1;
char w;
int main()
{
    scanf("%s",a+1);
    scanf("%s",b+1);
    for(;a[la];la++);
    for(;b[lb];lb++);
    la--;
    lb--;
    p[0]=1;
    for(int i=1;i<=max(la,lb);i++)
        p[i]=p[i-1]*base; 	   //进制
    if(a[1]>='A'&&a[1]<='Z')   //判断大小写
        w='A';
    else
        w='a';
    for(int i=la;i>=1;i--)
        h[i]=h[i+1]*base+a[i]-w+1; //求a字符串的哈希数组
    for(int i=lb;i>=1;i--)
        sum1=sum1*base+b[i]-w+1;   //求b字符串的哈希
    for(int i=1;i<=la-lb+3;i++)    //注意i必须小于等于la-lb 否则数组会越界
    {
        js1=h[i]-h[i+lb]*p[lb];    //判断是否相等
        if(js1==sum1)
            sum+=1;
    }
    cout<<sum<<endl;
}

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

题目

Given two strings a and b we define a * b to be their concatenation. For example, if a = “abc” and b = “def” then a * b = “abcdef”. If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = “” (the empty string) and a^(n+1) = a*(a^n).

输入

Each test case is a line of input representing s, a string of printable characters.

输出

For each s you should print the largest n such that s = a^n for some stringa. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case.

样例输入

abcd
aaaa
ababab

样例输出

1
4
3

解析

KMP算法的应用

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include 
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const ll N = 1005000;
ll Next[N];
char s[N];
char t[N];
ll  tlen,len;
void getNext(char s[N])
{
    ll j=0,k=-1;
    Next[0]=-1;
    while(j<tlen)
    {
        if(k==-1||s[j]==s[k])
        {
            Next[++j]=++k;
        }
        else
            k=Next[k];
    }
}
int main()
{
    while(1)
    {
        scanf("%s",s);
        if(s[0]=='.')
        break;
        tlen=strlen(s);
        len=tlen;
        getNext(s);
        ll kk=tlen-Next[tlen];
        if(strlen(s)%kk==0)
        {
            printf("%dn",strlen(s)/kk);
        }
        else
        { 
            printf("1n");   //如果不能除尽，说明有后缀，例如abababa，这种情况只能为1
        }
    }
    return 0;
}

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

题目

在CSP初赛后，chen03的RP快用完了。

RP是个神奇的东西。具体来说，chen03的RP值可以用二进制正整数a和十进制正整数n表示。他的RP值可以表示为
RP=axor(a<<1)xor(a<<2)xor…xor(a<<(n-1))。

其中a<

chen03想知道他的RP值是多少。

注：
1.将a左移i位，即在a后添加i个0，也可以看成a×2i，在C++中的运算符为<<；
2.按位异或：在二进制下，对两个数的每一位进行异或运算，并把结果放到答案的当前位上，在C++中的运算符为^。异或，即两个值同为1或同为0时结果为0，否则为1。

输入

共两行，第一行一个二进制正整数 a（保证不含前导 0），第二行一个十进制正整数 n，意义如题目描述。

输出

一行一个二进制正整数，表示 chen03 的 RP 值。答案不用取模。

样例输入

100001001
4

样例输出

111101110111

提示

解析

首先先简单介绍一下异或(xor)，异或共分为4种情况
0异或1等于1
1异或0等于1
0异或0等于0
1异或1等于0
异或最后结果只和1的个数有关，1为奇数个，结果就为1，1为偶数个，结果就为0，例如：
0 xor 0 xor 0 xor 1 = 1
0 xor 0 xor 1 xor 1 = 0
0 xor 0 xor 0 xor 1 xor 1 = 0

题目是指将一个2进制数进行向左移位求异或结果，下图就是对样例的解释，第一二三四行分别表示移动一位，两位，三位和四位，然后统计每一列中1的数目，如果1为奇数个，结果就为1，否则就为0.。

这个题目可以分为两种情况，样例是其中的一种情况，n的数目小于字符串的长度，另一种情况是大于，如
111
5
这种情况可以发现中间部分的结果全部相同，即如下图所示：

然后直接模拟这个过程，求每一列中1的个数即可。

代码

#include 
using namespace std;
typedef long long ll;
char a[1005000]={0};
int b[1005000]={0};
int c[1005000]={0};
int main()
{
    int n;
    scanf("%s",&a);
    scanf("%d",&n);
    int m=strlen(a);
    int p=n-m;
    queue<char>w;
    int sum1=0;
    for(int i=0;a[i];i++)
    {
        if(w.size()<n)
        {
            w.push(a[i]);
            if(a[i]=='1')
                sum1++;
            int k1=sum1%2;
            if(k1==1)
            {
                printf("1");
            }
            else
            {
                printf("0");
            }
        }
        else
        {
            int p=w.front();
            w.pop();
            if(p=='1')
                sum1--;
            w.push(a[i]);
            if(a[i]=='1')
                sum1++;
            int k1=sum1%2;
            if(k1==1)
            {
                printf("1");
            }
            else
            {
                printf("0");
            }
        }
    }
    for(int i=0;i<p;i++)
    {
        int k1=sum1%2;
        if(k1==1)
        {
            printf("1");
        }
        else
        {
            printf("0");
        }
    }
    while(w.size()!=1)
    {
        int p=w.front();
        w.pop();
        if(p=='1')
            sum1--;
        int k1=sum1%2;
        if(k1==1)
        {
            printf("1");
        }
        else
        {
            printf("0");
        }
    }
}

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

题目描述

The little cat is so famous, that many couples tramp over hill and dale to Byteland, and asked the little cat to give names to their newly-born babies. They seek the name, and at the same time seek the fame. In order to escape from such boring job, the innovative little cat works out an easy but fantastic algorithm:

Step1. Connect the father’s name and the mother’s name, to a new string S.
Step2. Find a proper prefix-suffix string of S (which is not only the prefix, but also the suffix of S).

Example: Father=‘ala’, Mother=‘la’, we have S = ‘ala’+‘la’ = ‘alala’. Potential prefix-suffix strings of S are {‘a’, ‘ala’, ‘alala’}. Given the string S, could you help the little cat to write a program to calculate the length of possible prefix-suffix strings of S? (He might thank you by giving your baby a name:)

输入

The input contains a number of test cases. Each test case occupies a single line that contains the string S described above.
Restrictions: Only lowercase letters may appear in the input. 1 <= Length of S <= 400000.

输出

For each test case, output a single line with integer numbers in increasing order, denoting the possible length of the new baby’s name.

样例输入

ababcababababcabab
aaaaa

样例输出

2 4 9 18
1 2 3 4 5

解析

kmp算法next数组的应用

#include
using namespace std;
char a[500500]={0};
int Next[500500]={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(scanf("%s",a)!=EOF)
    {
        getNext();
        int k=strlen(a);
        stack<int>w;
        while(k>=1)
        {
            w.push(k);
            k=Next[k];
        }
        while(!w.empty())
        {
            if(w.size()==1)
                cout<<w.top()<<endl;
            else
                cout<<w.top()<<' ';
            w.pop();
        }
    }
}