统计单词数

题意

不区分大小写统计一个完整单词在文章中出现的次数和第一次出现的字符位置。

思路

先将目标词和文章统一转小写。文章只含字母和空格，使用 split(" ") 能逐个检查完整单词；同时累计每段长度和一个分隔空格，即可得到每个单词的起始下标。

代码

Python代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14target = input().lower()
article = input().lower()

matches = []
position = 0
for word in article.split(" "):
    if word == target:
        matches.append(position)
    position += len(word) + 1

if matches:
    print(len(matches), matches[0])
else:
    print(-1)

C++代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73/* author: Rainboy email: rainboylvx@qq.com  time: 2021年 12月 05日 星期日 10:13:19 CST */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+5,maxe = 1e6+5; //点与边的数量

int n,m;

char word[10000000+5];
char s[10000000+5];

void to_lower(char c[],int len){
    // char c[] -- > char *c
    // *(c+x)   <-> c[x]
    // c[0]
    // c[1]
    // c[1001]
    for(int i=0;i<len;++i){
        char &x = c[i];
        if( x >='A' && x<='Z')
            x = x-'A' +'a';
    }
}
int len1,len2;
bool isque(int i){
    for( int j= 0;j< len1;j++){
        if( s[i+j] != word[j]){
            return false;
        }
    }
    //   s: abc xvc vec
    //work:     xvc
    //             ^ 这里是空格或末尾
    if( s[i+len1] == ' ' || i+len1 == len2)
        return true;
    return false;
}



int main(int argc,char * argv[]){
    cin.getline(word,sizeof(word));
    cin.getline(s,sizeof(s));

    len1 = strlen(word);
    len2 = strlen(s);
    to_lower(word, len1);
    to_lower(s, len2);

    // abc
    // 01234567->8
    //      abc

    int cnt = 0;
    int first =-1 ;
    for(int i = 0 ;i <=len2-len1 ;i++){
        if( i == 0 || s[i-1] == ' '){
            if( isque(i) ){
                cnt++;
                if(first == -1) 
                    first = i;
            }
        }
    }

    if( first == -1)
        std::cout << -1 ;
    else
        std::cout << cnt <<" "<< first << std::endl;


    return 0;
}

复杂度

时间复杂度为 $O(L)$ ， $L$ 为文章长度；空间复杂度为 $O(L)$ 。

总结

完整匹配应以单词为单位比较，而不是直接做子串查找。

目录

题意

思路

代码

Python代码

C++代码

复杂度

总结