Summer Training Team Selection (1) Problem D Hidden Password STL,字符串匹配,简单题

Source

2016 UESTC ACM Summer Training Team Selection (1)

ACM-ICPC 2015 Mid-Central Regional Problem D: Hidden Password

My Solution

先用map记录下来password中每个字母出现的次数；

然后去历遍message，如果当前访问的不是正在查找的，并且在map中的记录里不是0，那么FAIL

                                   如果是则，map里想要的字母--，然后查找password中的下一个字母

复杂度 O(n)

#include <iostream>
#include <cstdio>
#include <string>
#include <map>
using namespace std;
map<char, int> pw;

int main()
{
    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    #endif // LOCAL
    string password, line;
    cin>>password;
    cin>>line;
    int sz1 = password.size();
    int sz2 = line.size();
    int ptr = 0, fall = 1;
    for(int i = 0; i < sz1; i++){
        pw[password[i]]++;
    }
    for(int i = 0; i < sz2; i++){
        if(line[i] == password[ptr]){
            pw[password[ptr]]--;
            ptr++;
            if(ptr == sz1){
                fall = 0;
                break;
            }
        }
        else{
            if( pw[line[i]] != 0){
                fall = 1;
                break;
            }
        }
    }
    if(fall) printf("FAIL");
    else printf("PASS");
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx