求助,子串子序列求优化时间复杂度
  • 板块学术版
  • 楼主Hongfr
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/4/1 19:53
  • 上次更新2024/4/1 20:05:54
查看原帖
求助,子串子序列求优化时间复杂度
925109
Hongfr楼主2024/4/1 19:53

rt:

题目:

代码

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
string n;
int ans=1e9;
bool isSub(string s, string t) 
{
	int i=0,j=0;
	while (i<s.size() and j<t.size()) 
    {
		if (s[i]==t[j]) 
        {
			i++;
			j++;
		}
		else 
			j++;
	}
    if (i==s.size())
        return true;
	return false;
}

int main()
{
    cin>>n;
    for (int i=0;i<n.size();i++)
    {
        for (int j=i;j<n.size();j++)
        {
            string tmp="";
            for (int k=i;k<=j;k++)
                tmp+=n[k];
            int len=tmp.size();
            if (isSub("wotojo",tmp)==true)
            {
                // cout<<1;
                ans=min(ans,len);
            }
        }
    }
    cout<<ans;
}
2024/4/1 19:53
加载中...