Level2题解（1-10）

  2. 主页
  4. 文档
  6. Level2题解（1-10）
  8. 第9课 字符串应用

第9课 字符串应用

例题 1 字符串移位包含问题

定义一个循环移位操作: 将字符串的第一个字符移动到末尾形成新的字符串.

给定两个字符串s1和s2，要求判定其中一个字符串是否是另一字符串通过循环移位后的子字符串。

例如 CDAA是由 AABCD 两次移位后 BCDAA 的子串，而 ABCD 与 ACBD 不能通过移位来得到其中一个字符串是另一个字符串循环移位的子串。

Input

输入两个字符串组成。

Output

如果一个字符串是另一字符串通过循环移位的子串，则返回true，否则返回false。

分析

  1. 枚举所有的移位后的字符串, 然后查询s2是否在新的子串中. 时间复杂度O(nnm)
#include <iostream>
#include <cstring>
using namespace std;

char a[]="AABCD";
char b[]="CDAA";

int solve(char *a, char *b)
{
    int len = strlen(a);

    for(int i = 0; i < len; i++)
    {
        char tmp = a[0];
        for(int j=0; j < len-1; j++)
        {
            a[j] = a[j+1];
        }
        a[len-1] = tmp;
        if(strstr(a, b) != NULL)
            return 1;
    }
    return 0;
}

int main()
{

    if(solve(a, b))
        printf("ok\n");
    else
        printf("no\n");

    return 0;
}
  1. 可以把移位后字符串放在同一数组中, 这样时间复杂度 O(n*m)
#include <iostream>
#include <cstring>
using namespace std;

char a[200] = "AABCD";
char b[200] = "CDAA";

bool solve(char a[], char b[])
{
    //strcpy(a + strlen(a), a);
 strcat(a, a);
 if(strstr(a, b) != NULL)
  return true;
 else
  return false;
}

int main()
{
    if(solve(a, b))
        printf("ok\n");
    else
        printf("no\n");

    return 0;
}

例题 2 统计单词数

?P1308 统计单词数

题目描述

一般的文本编辑器都有查找单词的功能，该功能可以快速定位特定单词在文章中的位置，有的还能统计出特定单词在文章中出现的次数。

现在，请你编程实现这一功能，具体要求是：给定一个单词，请你输出它在给定的文章中出现的次数和第一次出现的位置。注意：匹配单词时，不区分大小写，但要求完全匹配，即给定单词必须与文章中的某一独立单词在不区分大小写的情况下完全相同（参见样例1 ），如果给定单词仅是文章中某一单词的一部分则不算匹配（参见样例2 ）。

输入格式

共2行。

第1行为一个字符串，其中只含字母，表示给定单词；

第2行为一个字符串，其中只可能包含字母和空格，表示给定的文章。

输出格式

一行，如果在文章中找到给定单词则输出两个整数，两个整数之间用一个空格隔开，分别是单词在文章中出现的次数和第一次出现的位置（即在文章中第一次出现时，单词首字母在文章中的位置，位置从0 开始）；如果单词在文章中没有出现，则直接输出一个整数-1。

输入输出样例

  • 输入 #1复制
To
to be or not to be is a question
  • 输出 #1复制

2 0

  • 输入 #2复制
to
Did the Ottoman Empire lose its power at that time
  • 输出 #2复制

-1

说明/提示

数据范围

1≤单词长度≤10。

1≤文章长度≤1,000,000。

noip2011普及组第2题

分析

  1. 有空格的字符串读入.
  2. 如何不分区大小写.
  3. 单词的匹配
  4. 更好的匹配办法??

参考代码

依次匹配每个单词

#include <cstdio>
#include <cstring>

char word[11];
char str[11];

int len, start=0, idx=0, count=0, pos=0, flag = 1;
char x;

int main(){
 scanf("%s", word);
 len = strlen(word);
 for(int i =0; i < len; i++){
  if(word[i] >= 'a' && word[i]<='z')
   word[i] = word[i] - 'a' + 'A';
 }

 getchar();

 while((x=getchar())!= EOF){
  pos++;
  if (x == ' ') {
   if(idx == len) {
    count++;
    if(count == 1)
     start = pos - len -1;
   }
   idx = 0;
   flag = 1;
   continue;
  }

  if(flag != 1)
   continue;

  if(x >= 'a' && x<='z')
   x = x - 'a' + 'A';

  if(x==word[idx]){
   idx++;
  } else {
   idx = 0;
   flag = 0;
  }
 }

 if(count)
  printf("%d %d", count, start);
 else
  printf("-1");

 return 0;
}


优化匹配:

#include <bits/stdc++.h>

char s[1000008], w[18];
int ls, lw;
char *p;
int pos, ans;

int main () {
    fgets(w+1, sizeof(w), stdin);
    fgets(s+1, sizeof(s), stdin);
    w[0] = ' ';
    s[0] = ' ';

  lw = strlen(w+1);
 ls = strlen(s+1);

    w[lw++] = ' ';
    w[lw] = '\0';

    s[ls++] = ' ';
    s[ls] = '\0';

    p = w;
    while(*p != '\0') {
     if(*p >= 'a' && *p <='z')
      *p = *p - 'a' + 'A';
     p++;
 }
 p = s;
 while(*p != '\0') {
     if(*p >= 'a' && *p <='z')
      *p = *p - 'a' + 'A';
     p++;
 }

 p = s;

 while(p = strstr(p, w)) {
  ans++;
  if(ans == 1)
   pos = p - s;
  p += lw - 1;
 }


    if(ans)//找到了
        printf("%d %d" , ans, pos);//输出
    else
        printf("-1");//输出-1

    return 0;
}

string

#include <iostream>
#include <string>
using namespace std;

string s, w;
int pos, ans;

int main(){
    getline(cin, w);
    getline(cin, s);

    for (int i = 0; i < w.size(); i++){
        w[i] = tolower(w[i]);
    }
    for (int i = 0; i < s.size(); i++){
        s[i] = tolower(s[i]);
    }

    w = ' ' + w + ' ';
    s = ' ' + s + ' ';

    int p = 0;
    while((p = s.find(w, p)) !=string::npos) {
  ans++;
  if(ans == 1)
   pos = p;
  p += w.size() - 1;
 }

    if(ans)
        cout << ans << " " << pos;
    else
        cout << -1;

    return 0;
}

例题 3 P1598 垂直柱状图

?P1598 垂直柱状图

题目描述

写一个程序从输入文件中去读取四行大写字母（全都是大写的，每行不超过100个字符），然后用柱状图输出每个字符在输入文件中出现的次数。严格地按照输出样例来安排你的输出格式。

输入格式

四行字符，由大写字母组成，每行不超过100个字符

输出格式

由若干行组成，前几行由空格和星号组成，最后一行则是由空格和字母组成的。在任何一行末尾不要打印不需要的多余空格。不要打印任何空行。

输入输出样例

  • 输入 #1复制
THE QUICK BROWN FOX JUMPED OVER THE LAZY DOG.
THIS IS AN EXAMPLE TO TEST FOR YOUR
HISTOGRAM PROGRAM.
HELLO!
  • 输出 #1复制
                            *
                            *
        *                   *
        *                   *     *   *
        *                   *     *   *
*       *     *             *     *   *
*       *     * *     * *   *     * * *
*       *   * * *     * *   * *   * * * *
*     * * * * * *     * * * * *   * * * *     * *
* * * * * * * * * * * * * * * * * * * * * * * * * *
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

说明/提示

每行输出后面不允许出现多余的空格。

分析

  1. 统计26个字母
  2. 找出出现的最大次数, 是这个图形的高度
  3. 给每个字母填上 *
  4. 找出每行的最后一个, 填上字符串结尾符.
  5. 输出

参考代码

#include <cstdio>
#include <cstring>
using namespace std;

int c[26] = {0,};
char x;
char p[400][53];
int max=0;

int main()
{
 for(int i=0; i < 4; i++){
  while(1) {
   x = getchar();
   if(x == EOF || x=='\n')
    break;
   if(x>='A' && x <='Z' ) {
    x= x- 'A';
    c[x]++;
   }
  }
 }

 for(int i =0; i < 26; i++) {
  if(max < c[i])
   max = c[i];
 }

 for(int i=0; i <=50; i++) {
  for(int j = 0 ; j <= max; j++) {
   p[j][i] = ' ';
  }

  if (i%2 == 0) {
   for(int j = 1 ; j <= c[i/2]; j++) {
    p[j][i] = '*';
   }
   p[0][i] = 'A' + i / 2;
  }
 }

 for(int j=max; j>=1 ; j--) {
  int flag = 0;
  for(int i =51; i>=0; i--) {
   if (p[j][i] != '*') {
     p[j][i] = '\0';
   } else {
    break;
   }
  }
 }

 p[0][51] = '\0';

 for(int j=max; j>=0 ; j--) {
  printf("%s\n", p[j]);
 }

 return 0;
}



作业

  • ?P1553 数字反转（升级版）
  • ?P1321 单词覆盖还原
  • ?P1603 斯诺登的密码
  • ?P1598 垂直柱状图
  • ?P1308 统计单词数

挑战题目:

  • ?P1101 单词方阵
  • ?P1071 潜伏者
  • ?P5587 打字练习
  • ?P1058 立体图
  • ?P1012 拼数