请选择 进入手机版 | 继续访问电脑版

滑动窗口:检测符合字符串字符数量的最短子串

[复制链接]
苍野狼步 发表于 2021-1-1 18:32:49 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
滑动窗口
[code]#include#include#includeusing namespace std;int start = 0;int len = INT_MAX;//返回效果void getRes(string& S,string& T) {        int left = 0, right = 0;        int valid = 0;//valid等于字符串的字符数了,就是匹配上了        unordered_map need, windows;        for (char i : T) need++;        while (right < S.size()) {//right等于S.size()时,竣事,即凌驾字符串索引                //窗口扩大                char c = S[right];                right++;                if (need.count(c)) {                        windows[c]++;                        if (need[c] == windows[c])                                 valid++;                 }                //窗口缩小                while (valid == need.size()) {                        if (right - left < len) {                                start = left;                                len = right - left;                        }                        char c = S[left];                        left++;                        if (need.count(c)) {                                if (windows[c] == need[c])                                        valid--;                                windows[c]--;                        }                }        }}int main() {        string s = "adafsasdfasfdsdsa";        string t="adsf";        getRes(s,t);        cout
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

发布主题

专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )