12785 - Emacs Plugin

All about problems in Volume 127. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
triplemzim
New poster
Posts: 48
Joined: Sat Apr 06, 2013 6:02 pm

Re: 12785 - Emacs Plugin

Post by triplemzim » Sun Sep 14, 2014 9:26 pm

I used KMP algorithm... but getting WA... tried every test cases I can think of... :(

Code: Select all

#include<bits/stdc++.h>

using namespace std;


#define ms(x,val) memset(x,val,sizeof(x))
#define ull unsigned long long
#define iii long long
#define pi acos(-1)
#define pb push_back
#define PII pair<int,int>
#define MP make_pair
#define eps 1e-9
#define inf 999999999
#define MAXN 1000009
#define MOD 1000000007 // 10^9 + 7


vector<int> cal_prefix_fun(string ch)
{
   int len=ch.length();
   int k=0;
   vector<int> v(len,0);
   for(int i=1;i<len;i++)
   {
       while(k>0 && ch[k]!=ch[i]) k=v[k];
       
       v[i]=k;
       if(ch[i]==ch[k]) k++;
   }

   return v;
} 

int substring_match(string ST,string sub_st,int start)
{
//    if(sub_st=="") return start;
    vector<int> v;
    v=cal_prefix_fun(sub_st);
    int k=0,len=ST.length(),m=sub_st.length();
    for(int i=start;i<len;i++)
    {
        while(k>0 && ST[i]!=sub_st[k]){

             k=v[k];
        }
        if(sub_st[k]==ST[i]) k++;
        if(k==m)
        {
            return i+1;
            k=v[k];
        }
    }
//    cout<<"return korlam"<<endl;
    return len+1;
}

int main()
{
 //   freopen("in.txt","r",stdin);
     
     

    string Main,sub,temp;
    int cases,mlen,idx,last,len;
    bool flag;
    while(scanf("%d",&cases)==1)
    {
        getchar();
        getline(cin,Main);
        mlen=Main.length();
        temp="";
        while(cases--)
        {
            flag=true;
            getline(cin,sub);
//            cin>>sub;
            len=sub.length();
            last=idx=0;
            temp="";

            for(int i=0;i<len;i++)
            {
                if(sub[i]=='*' && temp!="")
                {
                    idx=substring_match(Main,temp,last);
//                    cout<<"flag: "<<Main<<' '<<sub<<' '<<temp<<' '<<idx<<endl;
                  
                    temp="";
                    if(idx==mlen+1)
                    {
                        flag=false;
                        break;
                    }
                    else last=idx;
                    
                }
                else if(sub[i]!='*') temp+=sub[i];
            }
            if(temp!="")
            {
                idx=substring_match(Main,temp,last);
//                cout<<"last: "<<temp<<' '<<idx<<endl;
                if(idx==mlen+1)
                {
                    flag=false;
                }
            }


            if(flag) printf("yes\n");
            else printf("no\n");
        }
    }


    return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12785 - Emacs Plugin

Post by brianfry713 » Mon Sep 15, 2014 10:10 pm

Input:

Code: Select all

1
glrdtxijmxpmtnsotxbakvixwqahnbpvmiyhfjqsgiezvyqqvtrhozemsgufjlaxuafzjxtsfztcxjtuekbslifdobkymmxinciyadshdmkaxdvcpyucgbivesvrfszuvjuxnneszosytpakoxnuavpfpmywfzqalnzaadsbukznccaqbpkbmciboiaviqxtdwtfalgwxilzklrlaeomizqyhqupirkooftqscoqkzrwnljnpzcxysxiirxslkgbpatiehaqgtmtexjtwlsxfsfpjchwooxeqqowxomghybmvmhtzcqeuvvfadcotzulsihpytxitzuqndjnhcrdznjzsnqnomygxhyvcxdvwznmfyzmaqsafbbzqtmegmndtnaxkgsjhhvogubimvkuwmtohiunujsqwvnhbiqkrnzzhcivxspvgljqtfdppyhltxuwhkgyzfyghgceatzjekzzqepfcyqvvlrcxabxfzfphjtjdvujfvjvaaceytcwgvyfvbebcksjvlvagpkolvlnvorvjvrprqwmtbpwlhhivcjdutrhqduntnicjctcsponsgjdproktxopshwimsvfgfjrhctbujpmryshpgtldhaxrxfdpclxhuqpzlstxhhogzvxhpimyjjriqvzsizccptbblwateobfmandjzbulvebqduycycurgxcexxklaqxbfcmgeirbmtrrprunvqedniikgsxgkxjpzvyfdpgrizjxsdmotqrizbshwrpgozyouwvalcrwbavufikaabibfckbuajkzhavfwxtyprzrmvzwfzzjkaoolpknyvoivjprjirazrrooskusjdemtszkdmiaasvlipusguuzoiogukygpesixrscfccfvxqfolzvftuvdkcaucgjhatgrliyokdljtsygrvonrjqelqaoymxyfdrrlphxsugomgufdisxslbfdbtcnqattumgjvdepmsbuoiaxbxroywrzstpkwigqwobrsfggzjcorcnubeizcabwvqjrapjydlpxsxfsgigzmtuozepdgqccilvkafifszfkwkceukehfaxegmknfmrnzmabrkgjklwiwynqjtzotwvbjhoovfdusfvlqdxcptkntxfcqftldonmxdcsjimdpjqfmpjbiuqerygkfbvipkxmobgzjsezdugqkqtukkydkhppknxaxuonwxohpsitnplzhevtqwwafoppbprajiohfcrwxzrmqclzjiszerclfrbggsgsawbhbueywvkoaxojhgkmzmxegamotvgvrkdugjscgergdfplnczpoytuzijudrpwdurkdlmksfsvmkiamhpagkxhsgbvzsudplnuyzgqfzorjwtxekzmvwvpeyneshhhuwcsvkjcjxwuvrtbctpzrkowidcbkjk
hhu*v
Output should be yes
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 127 (12700-12799)”