几道比较有意思的字符串题

 Algorithm
 

整数反转求和

  • 描述：

请您写一个reverseAdd函数，该函数分别将输入的两个正整数a和b的数字按照高位在右的方式反转求和。
例如，reverseAdd(123,456)=321+654=975。

  • 输入：

两个正整数a和b，以空格分隔，$1 \le a,b \le 70000$。

  • 输出：

输出一个整数，表示两个正整数反转求和的结果。

  • 样例输入：

123 456

  • 样例输出：

975

  • 解题思路：

按照int型来处理两个输入参数会比较麻烦，按照字符串类型来处理两个输入参数则会大大简化处理过程。

  • 参考代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
using namespace std;

int main() {
    string n,m;
    while(cin>>n>>m) {
        int x=0,y=0,i;
        if(m[0]=='0'&&n[0]=='0')
            break;
        for(i=m.size()-1;i>=0;i--)
            x=x*10+m[i]-'0';
        for(i=n.size()-1;i>=0;i--)
            y=y*10+n[i]-'0';
        cout<<x+y<<endl;
    }
    return 0;
}

字符串计数

  • 描述：

给定一个仅由小写字母组成且长度不超过106的字符串，将首字符移到末尾并记录所得的字符串，不断重复该操作，虽然记录了无限个字符串，但其中不同字符串的数目却是有限的，那么一共记录了多少个不同的字符串？

  • 输入：

给定的字符串。

  • 输出：

记录的不同字符串数目。

  • 输入样例：

abab

  • 输出样例：

2

  • 解题思路：

模板题，考查KMP算法next数组的求解

  • 参考代码：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    #include<bits/stdc++.h>
    using namespace std;

    const int N=1000007;
    char s[N];
    int next[N];

    int main() {
        scanf("%s",s);
        int n=strlen(s);
        next[0]=-1;
        for(int i=0,j=-1;i<n;)
            if(j==-1||s[i]=s[j]) next[++i]=++j;
            else j=next[j];
        if(n%(n-next[n])) printf("%d",n)
        else printf("%d",n-next[n]);
        return 0;
    }
 Previous

Knapsack