Sicily 1252 Defining Moment (SOJ 1252)「暴力匹配」

0.00 avg. rating (0% score) - 0 votes
转载请注明: 吹水小镇 | reetsee.com
原文链接地址: http://blog.reetsee.com/archives/168

原题地址:点击打开链接

好久没有做题了,发现果然还是很喜欢做题啊···耐没做手生,所以挑了一题水一点的。这题按道理来说有比较优雅的解法,但是我懒就直接敲了暴力了,直接全部使用if语句来匹配,匹配的时候也没有考虑效率,直接使用的是C++ string里面的“substr”方法,如果说数据规模大一点的话,或者说给出的字典规模大一点,初步想法可以使用树结构(字典树是什么?我去查一下先)来匹配前缀或者后缀。

代码写得很丑,因为我以为是可以无限匹配的,就是说我原本以为antiantiantiaererer会得出“aginst aginst aginst one who one who one who asss”,wrong answer后才发现原来前缀和后缀最多只扩展一次。所以有很多代码就废了,我还用了deque呃·····

代码不具有参考性,因为实在太难看不过太懒了也就懒得去改,各位自己写会更加漂亮一点:

#include<queue>
#include<vector>
#include<deque>
#include<string>
#include<stdio.h>
#include<iostream>
using namespace std;
int tc;
string s;
string pres[9]={"against ","after ","before ","not ",
                "one who ","to actively ","change into ",
                "multiple instances of ","the process of "};
string posts[3]={" again","s","ing"};
int h,t;
deque<string> ft;
deque<string> bk;
void ftEn(int index)
{
    ft.push_back(pres[index]);
}
void bkEn(int index)
{
    bk.push_front(posts[index]);
}
bool checkPre(string ss)
{
    string stmp;
    if(ss.size()>3)
    {
        stmp=ss.substr(0,4);
        if(stmp=="anti")
        {   
            ftEn(0);
            s=ss.substr(4,s.size()-4);
            return true;
        }
        else if(stmp=="post")
        {
            ftEn(1);
            s=ss.substr(4,s.size()-4);
            return true;
        }
    }

    if(ss.size()>2)
    {
        stmp=ss.substr(0,3);
        if(stmp=="pre")
        {
            ftEn(2);
            s=ss.substr(3,s.size()-3);
            return true;
        }
    }
    
    if(ss.size()>1)
    {
        stmp=ss.substr(0,2);
        if(stmp=="re")
        {
            bkEn(0);
            s=ss.substr(2,s.size()-2);
            return true;
        }
        else if(stmp=="un")
        {
            ftEn(3);
            s=ss.substr(2,s.size()-2);
            return true;
        }
    }
    return false;
}
bool checkPost(string ss)
{
    string stmp;
    int st=ss.size()-2;
    if(st>=0)
    {   
        stmp=ss.substr(st,2);
        if(stmp=="er")
        {
            ftEn(4);
            bkEn(1);
            s=ss.substr(0,st);
            return true;
        }
    }

    st=ss.size()-3;
    if(st>=0)
    {
        stmp=ss.substr(st,3);
        if(stmp=="ing")
        {
            ftEn(5);
            s=ss.substr(0,st);
            return true;
        }
        else if(stmp=="ize")
        {
            ftEn(6);
            s=ss.substr(0,st);
            return true;
        }
    }

    st=ss.size()-1;
    if(st>=0)
    {
        stmp=ss.substr(st,1);
        if(stmp=="s")
        {
            ftEn(7);
            s=ss.substr(0,st);
            return true;
        }
    }

    st=ss.size()-4;
    if(st>=0)
    {
        stmp=ss.substr(st,4);
        if(stmp=="tion")
        {
            ftEn(8);
            bkEn(2);
            s=ss.substr(0,st);
            return true;
        }
    }
    return false;
}
int main()
{
  //freopen("in.txt","r",stdin);
  //freopen("out","w",stdout);
    cin>>tc;
    while(tc--)
    {
        ft.clear();
        bk.clear();
        cin>>s;
        h=0; t=s.size();
        checkPre(s);
        checkPost(s);
        for(int i=0;i<ft.size();++i)
            cout<<ft[i];
        cout<<s;
        for(int i=0;i<bk.size();++i)
            cout<<bk[i];
        cout<<endl;
    }
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注