Description
In other words, the last time Tushan Xiaoba entered the "Gate of Time and Space", it was not to return to the real world, but a rectangular cabin. As the door of time and space slowly closed, Xiao Ba could see many strange characters on the wall. Strangely enough, there was a voice in the cabin.
"You should have returned to the real world now, but you've been here too long, and you've run out of energy, and you can't go directly through the gate of time and space, so you're here. The only way to do this is to gain Barala's energy, otherwise you will remain here forever."
"How to get Barala energy?"
"See the Barala ciphertext on the wall? Now I'll give you a key of energy. Find out the barala energy string from the barala ciphertext and get the barala energy. Barala energy string is the smallest string of all the keys containing energy. Remember, if you find a number of barala energy strings that meet the requirements, don't be greedy, just take the first one, or you'll lose all your previous work."
Input
There are many groups of input data, each group of data input the first line of input string Barala ciphertext S, the second line of input string energy key T, S length lens (1 < lens < 105)
T-length lent (1 < lent < 105) (input does not contain spaces), and input characters are case-sensitive.
Output
For each group of input data, the output of the Barala energy string found, each group of output occupies one line. If you can't find the Barala energy string, output a blank line.
Sample Input
ADOBECODEBANC ABC ABCDA BD
Sample Output
BANC BCD
thinking
Given two strings S and T, ask S for the position with the smallest length at the front.
Substring containing T, if it does not exist, only output newline
First of all, O(N2) complexity can't be overwhelmed. We have to find an optimization method.
Store the number of occurrences of characters in the T-string and whether they have occurred with two tag arrays, respectively
Use l to record the current position of the left endpoint, min to record the updated position of the left endpoint, min to record the required length of the substring, and cnt to record the current occurrence of several characters in the T-string.
Then traverse the S-string, skip the characters that have not appeared, and encounter the characters that have appeared, give him the number of occurrences - 1. When subtracted by one, determine whether the current occurrence number is >= 0. If so, record it with cnt. When the number of CNTs is the same as the length of the T-string, it means that there is already an interval containing the T-string. We try to change it according to the current left and right endpoints. New interval, then move the left boundary to the right. In the process of moving the left boundary to the right, if you encounter a character that has already appeared in the T string, give it the number of occurrences + 1. When the number of occurrences is added to the positive number, the value of CNT decreases by one (our interval does not contain all the characters in the T string at present), so move the left boundary to the right and stop, continue to look at the right boundary, until the whole T string is included, and then Then try to update the left boundary...
The general idea is to enumerate the intervals containing T strings, then update the boundaries to find the smallest one.
In this way, the required substrings are obtained with linear complexity, and the final output of the found interval string is the answer.
Still can use STL map to do, the idea is the same.
Code 1
#include <cstdio>
#include <cstring>
#include <cctype>
#include <string>
#include <set>
#include <iostream>
#include <stack>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
using namespace std;
const int N=1e5+20;
char s[N],t[N];
int vis[200];//Number of occurrences of markers
int sear[200];//Has the tag ever appeared?
int main()
{
while(~scanf("%s%s",s,t))
{
mem(vis,0);
mem(sear,0);
int tlen=strlen(t);
int slen=strlen(s);
for(int i=0; i<tlen; i++)
{
vis[t[i]]++;
sear[t[i]]=1;
}
int cnt=0,l=0,minl=0,minn=slen+1;
for(int r=0; r<slen; r++)
if(sear[s[r]])
{
if(--vis[s[r]]>=0)
cnt++;
while(cnt==tlen)
{
if(r-l+1<minn)
minl=l,minn=r-l+1;
if(sear[s[l]])
if(++vis[s[l]]>0)
cnt--;
l++;
}
}
if(minn>slen) printf("\n");
else
{
for(int i=minl; i<minl+minn; i++)
printf("%c",s[i]);
printf("\n");
}
}
return 0;
}
Code 2
#include <stdio.h>
#include <iostream>
#include <string>
#include <map>
using namespace std;
string minWindow(string S, string T)
{
map<char, int> m;
for(int i = 0; i < T.size(); ++ i)
m[T[i]]++;
int cnt = 0, l = 0, minl = 0, minsize = S.size() + 1;
for(int r = 0; r < S.size(); ++ r)
if(m.find(S[r]) != m.end())
{
if(-- m[S[r]] >= 0)
++ cnt;
while(cnt == T.size())
{
if(r - l + 1 < minsize)
minl = l, minsize = r - l + 1;
if(m.find(S[l]) != m.end())
if(++ m[S[l]] > 0)
-- cnt;
++ l;
}
}
if(minsize>S.size())
return "";
return S.substr(minl, minsize);
}
int main()
{
string s, t;
while(cin >> s >> t)
{
string ans = minWindow(s, t);
cout << ans << endl;
}
return 0;
}