欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

智算之道2020第一场比赛C题

程序员文章站 2022-05-12 11:43:20
...

这题博主只通过了80qwq,所以该篇仅仅供参考思路,请勿模仿。
智算之道2020第一场比赛C题
0、如果字符串S长度大于字符串T的长度,肯定为0,直接输出0,然后结束。
1、该题我想的是,既然是判断所有排列情况是否是子串,那么我们就不可能将所有排列列出来,肯定会特别复杂,那么我们可以换一种思路,当字符串S中的每种字母的数量和字符串T的子串的每种字母的数量完全相同时,就是一种情况。
2、然后我还用vector定义了一个string的动态数组,用于保存找到的符合情况的子串,用来查重,当遍历完,发现是新的情况时,将新的子串保存进去,然后数目+1,否则无视,进行下一次判断。

#include<iostream>
#include<string>
#include<string.h>
#include<vector>
using namespace std;

vector <string> s;

vector <int> num1(24);
bool fun(string* b,int len)
{
    vector <int> num2(24);
    string l="";
    l.append(*b,0, len);
    for (int x = 0; x < len; x++)
    {
        num2[(*b)[x] - 'a']++;
    }
    int i = 1;
    for (int x = 0; x < 24; x++)
    {
        if (num1[x] != num2[x])
        {
            i = 0;
            break;
        }
    }
    if (i)
    {
        int j = 1;
        for (int x = 0; x < s.size(); x++)
        {
            if (strcmp(l.c_str(), s[x].c_str()) == 0)
            {
                j = 0;
                break;
            }
        }
        if (j)
        {
            s.push_back(l);
            return true;
        }
    }
        return false;
}
int main()
{
    int res = 0;
    string a, b;
    cin >> a >> b;
    int a_len = a.length();
    int b_len = b.length();
    if (a_len > b_len)
    {
        cout << 0;
        return 0;
    }
    for (int x = 0; x < a_len; x++)
    {
        num1[a[x] - 'a']++;
    }
    string* l = &b;
    for (int x = 0; x < b_len - a_len+1; x++)
    {
        bool Y_N=fun(l, a_len);
        if (Y_N == true)
        {
            ++res;
        }
        l->erase(0,1);
    }
    cout << res;
    return 0;
}