StringSubstitutor默认值null（string的默认值）

25-02-10 17

本篇文章给大家谈谈StringSubstitutor默认值null，以及string的默认值的知识点，同时本文还将给你拓展#Leetcode#1016.BinaryStringWithSubstrin

本篇文章给大家谈谈StringSubstitutor默认值null，以及string的默认值的知识点，同时本文还将给你拓展#Leetcode# 1016. Binary String With Substrings Representing 1 To N、B - Substrings Sort、CF 914F Substrings in a String——bitset处理匹配、Codeforces 914F. Substrings in a String（bitset）等相关知识，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

StringSubstitutor默认值null（string的默认值）
#Leetcode# 1016. Binary String With Substrings Representing 1 To N
B - Substrings Sort
CF 914F Substrings in a String——bitset处理匹配
Codeforces 914F. Substrings in a String（bitset）

StringSubstitutor默认值null（string的默认值）

"extensionFact": {
  "type": "${type:-}",
  "extension": ${"extension":-null}
},

#Leetcode# 1016. Binary String With Substrings Representing 1 To N

https://leetcode.com/problems/binary-string-with-substrings-representing-1-to-n/

Given a binary string S (a string consisting only of ‘0‘ and ‘1‘s) and a positive integer N,return true if and only if for every integer X from 1 to N,the binary representation of X is a substring of S.

Example 1:

Input: S = "0110",N = 3 Output: true

Example 2:

Input: S = "0110",N = 4 Output: false

Note:

1 <= S.length <= 1000
1 <= N <= 10^9

代码：

class Solution {
public:
    bool queryString(string S,int N) {
        int num;
        int len = S.length();
        
        for(int i = 0; i <= N; i ++) {
            string t = Binary(i);
            if(S.find(t) == -1) return false;
        }
        return true;
    }
    string Binary(int x) {
        string ans = "";
        while(x) {
            ans += x % 2 + ‘0‘;
             x /= 2;
        }
        for(int i = 0; i < ans.size() / 2; i ++) 
            swap(ans[i],ans[ans.size() - i - 1]);
        return ans;
    }
};

　　五题打卡

B - Substrings Sort

Problem description

You are given nn strings. Each string consists of lowercase English letters. Rearrange (reorder) the given strings in such a way that for every string, all strings that are placed before it are its substrings.

String a is a substring of string b if it is possible to choose several consecutiveletters in b in such a way that they form a. For example, string "for" is contained as a substring in strings "codeforces", "for" and "therefore", but is not contained as a substring in strings "four", "fofo" and "rof".

Input

The first line contains an integer nn (1≤n≤100) — the number of strings.

The next nn lines contain the given strings. The number of letters in each string is from 1 to 100, inclusive. Each string consists of lowercase English letters.

Some strings might be equal.

Output

If it is impossible to reorder nn given strings in required order, print "NO" (without quotes).

Otherwise print "YES" (without quotes) and nn given strings in required order.

Examples

Input

5
a
aba
abacaba
ba
aba

Output

YES
a
ba
aba
aba
abacaba

Input

5
a
abacaba
ba
aba
abab

Output

NO

Input

3
qwerty
qwerty
qwerty

Output

YES
qwerty
qwerty
qwerty

Note

In the second example you cannot reorder the strings because the string "abab" is not a substring of the string "abacaba".

解题思路：C语言中strstr(str1,str2) 函数用于判断字符串str2是否是str1的子串。如果是，则该函数返回str2在str1中首次出现的地址；否则，返回NULL。了解了这个函数，这道题就非常简单。只要将字符串的长度按升序排列，然后从第二个字符串开始依次检查当前字符串是否含有前一个字符串，即如果strstr(str1,str2)都不为NULL，就满足所有条件输出"YES"，否则输出"NO"。

AC代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 struct NODE{
 4     char str[105];
 5     int len;
 6 }node[105];
 7 bool cmp(NODE a,NODE b){return a.len<b.len;}
 8 int main(){
 9     int n;
10     cin>>n;getchar();
11     for(int i=0;i<n;++i){
12         cin>>node[i].str;
13         node[i].len=strlen(node[i].str);
14     }
15     sort(node,node+n,cmp);
16     bool flag=false;
17     for(int i=1;i<n;++i)
18         if(strstr(node[i].str,node[i-1].str)==NULL){flag=true;break;}
19     if(flag)cout<<"NO"<<endl;
20     else{
21         cout<<"YES"<<endl;
22         for(int i=0;i<n;++i)
23             cout<<node[i].str<<endl;
24     }
25     return 0;
26 }

C++的string类提供了字符串中查找另一个字符串的函数find。其重载形式为：string::size_type string::find(string &);功能为在string对象中，查找参数string类型的字符串是否存在，如果存在，返回起始位置。不存在则返回 string::npos。因此，此题还可以用这个来判断。

AC代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 struct NODE{
 4     string str;
 5     int len;
 6 }node[105];
 7 bool cmp(NODE a,NODE b){return a.len<b.len;}
 8 int main(){
 9     int n;
10     cin>>n;getchar();
11     for(int i=0;i<n;++i){
12         cin>>node[i].str;
13         node[i].len=node[i].str.length();
14     }
15     sort(node,node+n,cmp);
16     bool flag=false;
17     for(int i=1;i<n;++i)
18         if(node[i].str.find(node[i-1].str)==string::npos){flag=true;break;}
19     if(flag)cout<<"NO"<<endl;
20     else{
21         cout<<"YES"<<endl;
22         for(int i=0;i<n;++i)
23             cout<<node[i].str<<endl;
24     }
25     return 0;
26 }

CF 914F Substrings in a String——bitset处理匹配

题目：http://codeforces.com/contest/914/problem/F

可以对原字符串的每种字母开一个 bitset 。第 i 位的 1 表示这种字母在第 i 位出现了。

考虑能不能匹配上，可以把可行的 “开头” 设成 1 ；

这样的话，枚举到匹配串的第 i 位，字符是 ch，就找出原字符串里 ch 对应的那个 bitset ，则 bt[ ch ] >> ( i-1 ) 的这些位置可以是合法的开头；

所以每次 ans 每个位置都赋成 1 ，然后对于匹配串的每个位置， & 一下 bt[ ch ] >> ( i-1 ) ，最后看看对应区间里有几个合法的开头就行啦！

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
using namespace std;
const int N=1e5+5,K=30;
int n; char s[N],ch[N];
bitset<N> bt[K],ans,ini;
int main()
{
  scanf("%s",ch+1); n=strlen(ch+1);
  for(int i=1;i<=n;i++)
    bt[ch[i]-‘a‘][i]=1;
  for(int i=1;i<=n;i++)ini[i]=1;
  int Q,op,u,l,r,m; char tp[5];
  scanf("%d",&Q);
  while(Q--)
    {
      scanf("%d",&op);
      if(op==1)
    {
      scanf("%d",&u);scanf("%s",tp);
      bt[ch[u]-‘a‘][u]=0;
      ch[u]=tp[0];
      bt[ch[u]-‘a‘][u]=1;
    }
      else
    {
      scanf("%d%d",&l,&r);scanf("%s",s);
      ans=ini; m=strlen(s);
      if(m>r-l+1){puts("0");continue;}
      for(int i=0;i<m;i++)
        ans&=(bt[s[i]-‘a‘]>>i);
      int d=(ans>>l).count() - (ans>>(r-m+2)).count();
      printf("%d\n",d);
    }
    }
  return 0;
}

Codeforces 914F. Substrings in a String（bitset）

　　比赛的时候怎么没看这题啊... 血亏 T T

　　对每种字符建一个 bitset，修改直接改就好了，查询一个区间的时候对查询字符串的每种字符错位 and 一下，然后用 biset 的 count 就可以得到答案了。。。

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<bitset>
#define ll long long
using namespace std;
const int maxn=100010, inf=1e9;
int n, ty, l, r, x;
bitset<maxn>v[26], ans;
char s[maxn], s2[maxn], c;
inline void read(int &k)
{
    int f=1; k=0; char c=getchar();
    while(c<''0'' || c>''9'') c==''-''&&(f=-1), c=getchar();
    while(c<=''9'' && c>=''0'') k=k*10+c-''0'', c=getchar();
    k*=f;    
} 
int main()
{
    scanf("%s", s+1); int len=strlen(s+1);
    for(int i=1;i<=len;i++) v[s[i]-''a''][i]=1;
    read(n);
    for(int i=1;i<=n;i++)
    {
        read(ty);
        if(ty==1)
        {
            read(x); scanf("%c", &c);
            v[s[x]-''a''][x]=0;
            v[(s[x]=c)-''a''][x]=1;
        }
        else
        {
            read(l); read(r);
            scanf("%s", s2); int m=strlen(s2);
            if(r-l+1<m) {puts("0"); continue;}
            ans.set();
            for(int j=0;j<m;j++) ans&=(v[s2[j]-''a'']>>j);
            printf("%d\n", (int)(ans>>(l)).count()-(int)(ans>>(r-m+2)).count());
        }
    }
}

View Code

今天关于StringSubstitutor默认值null和string的默认值的介绍到此结束，谢谢您的阅读，有关#Leetcode# 1016. Binary String With Substrings Representing 1 To N、B - Substrings Sort、CF 914F Substrings in a String——bitset处理匹配、Codeforces 914F. Substrings in a String（bitset）等更多相关知识的信息可以在本站进行查询。

本文标签：