스트링이 주어진 패턴을 반복하는지 확인하기

주어진 패턴을 주어진 스트링이 따르는지 확인한다.

패턴 : abba , 스트링 :  redbluebluered >> 1

패턴 : aaaa, 스트링 : asdasdasdasd >> 0

나이브 솔루션 :

패턴 첫 글자를 매칭해서 맵에 넣는다(임의로 잘른 모든 경우에 대해). 그리고 남은 스트링과 패턴에 대해 같은 작업을 반복한다.

남은 스트링이 없는데 패턴이 남으면 0 리턴, 다음 패턴이 이미 있는 패턴이면 그걸 적용해 보고 안되면 0. 스트링과 패턴이 전부 0이면 그때 1

최악의 경우 O(N^N) 이런거 막 나올수 있겠다. 가능은 함.

bool isMatch(string str, int iStr, string ptn, int iPtn, unordered_map<char, string> &hmap){
    if(iStr == str.size() && iPtn == ptn.size()) return true;
    if(iStr == str.size() || iPtn == ptn.size()) return false;
    char c = ptn[iPtn];
    if(hmap.find(c)!=hmap.end()){
        string toMatch = hmap[c];
        for (int i = 0; i < toMatch.size(); i++) {
            if (iStr >= str.size() || str[iStr] != toMatch[i])
                return false;
            istr++;
        }
        return isMatch(str, istr, ptn, iPtn+1, hmap);
    }
    //try all possiblities
    bool flag = false;
    for (int i = iStr; i < str.size(); i++){
        hash[c] = str.substr(iStr, i - iStr + 1);
        flag |= isMatch(str, i + 1, ptn, iPtn + 1, hmap);
        hmap.erase(c);
        if(flag) return true;
    }
    return false;
}

bool isMatch(string str, string ptn){
    if(str.size()<ptn.size()) return false;
    if(ptn.empty()) return str.empty()? true : false;
    if(ptn.size()==1) return  str.size()>;1? true : false;
    unordered_map<char, string> hmap;
    return isMatch(str, 0, ptn, 0, hmap);
}

성질을 이용한 솔루션 :

관찰 : 반복하지 않는 패턴은 그냥 완충용이다. 1 이상의 크기만 있으면 된다. 중요한건 반복하는 원소들 뿐이다.

모든 섭스트링의 갯수가 N^2 밖에 없다는 점을 생각해 보면, 해당 패턴을 맞추는지 확인하기 위해 확인해야 할 섭스트링의 총수 역시 저거밖에 안되는데 , 심지어 겹치지 않게 할 섭스트링은 더더욱 적다!!

섭스트링을 멀티셋같은거에 전부 밀어넣은 후에, 패턴을 만족하는 "갯수"가 있는지 확인해 보자(예 : a 3개 b 2개짜리 있나?)

>> 있으면 그것들의 인덱스를 확인해서 패턴과 일치할 수 있는지 확인한다.

모든 가능한 경우에 대해 확인한다.

많아야 N개를 넘지 않을 것이다. 후보가. 각 후보를 확인하는 데에 N 정도의 시간이 걸리니 총 대략 O(N^2) 짜리 알고리즘이 되겠다!!

패턴의 종류는 26개를 넘지 않는다고 가정한다.

bool matchespatern(string s, string p){

// parse p and count duplicates

vector<int> counter(26,0);

for(int i = 0 ; i < s.size() ; i++){

counter[s[i]-'a']++;

}

int curr = 0;

unordered_map<char,int> duplicates;

while(curr<s.size()){

if(counter[s[curr]-'a']==1){

if(curr!=0&&s[curr-1]=='.'){

s.erase(s.begin()+curr);

continue;

}

s[curr] = '.';

}else{

duplicates.insert(pair<char,int>(s[curr],counter[s[curr]-'a']));

}

curr++;

}

// parse string to substrings

unordered_map<string , vector<int>> subs;

for(int i = 0 ; i < s.size() ; i++){

for(int j = 0 ; j < s.size() ; j++){

auto it = subs.find(string(s.begin()+i,s.begin()+j+1);

if(it!=subs.end()) it->second.push_back(i);

else subs.insert(pair<string,int>(string(s.begin()+i,s.begin()+j+1),vector<int>(1,i)));

}

}

unordered_multimap<int,string> subcount;

for(auto it = subs.begin() ; it!=subs.end() ; it++){

subcount.insert(pair<int,string>(it->second->size(),it->first);

}

unordered_multimap<int,char> dupcount;

for(auto it = duplicates.begin() ; it!=duplicates.end() ; it++){

dupcount.insert(pair<int,string>(it->second,it->first);

}

// match dupcount from subcounts

return selectandmatch(dupcount,subcount,subs,s,p,vector<string>(26,""));

}

bool selectandmatch(unordered_multimap<int,char> dup, unordered_multimap<int,string> sub, unordered_map<string,vector<int>> & subs, string &s, string &p, vector<string> & match){

if(dup.size()==0){

// matched all elements. use match vector to check

return ismatch(s,p,subs,match);

}

// match elements

auto it = dup.begin();

auto it2 = sub.equal_range(it->first);

bool ret = false;

for(auto it3 = it2.first ; it3 != it2.second ; it3++){

match[it->second-'a'] = it3->second;

ret |= selectandmatch(dup,sub,subs,s,p,match);

}

return ret;

}

bool ismatch(string & s, string & p , unordered_map<string,vector<int>> & subs, vector<string> & match){

vector<char> marker(s.size(),'.');

for(int i = 0 ; i < 26 ; i++){

if(match[i]!=""){

auto it = subs.find(match[i]);

for(int k = 0 ; k < it->second.size() ; k++){

for(int j = it->second[k] ; j <match[i].size() ; j++){

marker[j] = i+'a';

}

}

}

}

// check for final match

string final = marker[0];

for(int i = 1 ; i < marker.size() ; i++){
    if(marker[i-1]!=marker[i]) final+= marker[i];

}

return final==p;

}

예상 시간 복잡도 O(N^2 * a )

공간 복잡도 O(N)