AC自動(dòng)機(jī)_重疊與非重疊匹配

  • 可重疊與不可重疊匹配
      比如模式串為aba,字符串為abababab,若可重疊匹配,那么aba出現(xiàn)的次數(shù)為三次;若為不可重疊匹配,那么出現(xiàn)的次數(shù)為兩次: aba / b / aba /b
       AC自動(dòng)機(jī)對(duì)于可重疊匹配很方便,直接順著節(jié)點(diǎn)的fail指針一直走就可以.

不可重疊匹配
Searching the String
題意:
有若干個(gè)模式串,然后在字符串中查詢(xún)它們出現(xiàn)的次數(shù).但是0表示可以重疊出現(xiàn),1表示不可以重疊出現(xiàn);
題解:
 假設(shè)字典樹(shù)的每個(gè)單詞尾節(jié)點(diǎn)都有個(gè)變量為pos,記錄最后一次匹配主串的位置;
 對(duì)于可重疊匹配,直接順著自動(dòng)機(jī)的fail指針一直走;
 對(duì)于不可重疊匹配,如果當(dāng)前正在匹配主串的位置-最后一次成功匹配的字符串的位置大于等于單詞的長(zhǎng)度,那么這樣的匹配是可行的;
 比如模式串為aba,字符串為abababab,第一次匹配到aba的位置為2;第二次匹配到aba位置為4,但是4-2<3,所以這次的匹配是無(wú)效的;第三次匹配到aba位置為6,6-2=4>=3,成功匹配;所以最后成功匹配次數(shù)為2

/*    這題數(shù)據(jù)有點(diǎn)惡心,模式串會(huì)重復(fù)出現(xiàn)
input:
ab
4  
0 ab  
1 ab  
0 ab  
1 ab  
output:
Case 1
1
1
1
1

*/  
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
const int MAXN=100010;
const int BASE=26;
struct Node
{
    int fail;
    int next[26];
    bool ed;
    int len;
    int id1;
    int id2;
    int pos;
    void init()
    {
        fail=0;
        ed=false;
        len=pos=-1;
        id1=id2=0;
        memset(next,0,sizeof(next));
    }
};
Node trie[600005];
int trie_s;
int *x[MAXN];
char str[MAXN];
void put(char *str,int choose,int id)
{
    int p=1;
    int len=strlen(str);
    for(int i=0;i<len;i++)
    {
        int pos=str[i]-'a';
        if(trie[p].next[pos]==0)
        {
            trie[p].next[pos]=++trie_s;
            trie[trie_s].init();
        }
        p=trie[p].next[pos];
    }
    trie[p].ed=true;
    trie[p].len=len;
    if(choose==0)
    {
        x[id]=&(trie[p].id1);
    }
    else x[id]=&(trie[p].id2);
}
void getFail()
{
    queue<int> que;
    int son,p=1,temp;
    que.push(p);
    while(!que.empty())
    {
        int curr=que.front();
        que.pop();
        for(int i=0;i<26;i++)
        {
            son=trie[curr].next[i];
            if(son)
            {
                if(curr==1) trie[son].fail=1;
                else
                {
                    temp=trie[curr].fail;
                    while(temp!=0)
                    {
                        if(trie[temp].next[i])
                        {
                            trie[son].fail=trie[temp].next[i];
                            break;
                        }
                        temp=trie[temp].fail;
                    }
                    if(temp==0) trie[son].fail=1;
                }
                que.push(son);
            }
        }
    }
}
void query(char *str)
{
    int len=strlen(str);
    int p=1,temp;
    for(int i=0;i<len;i++)
    {
        int pos=str[i]-'a';
        while(!trie[p].next[pos]&&p!=1) p=trie[p].fail;
        p=trie[p].next[pos];
        if(p==0) p=1;
        temp=p;
        while(temp!=1)
        {
            if(trie[temp].ed)
            {
                trie[temp].id1=trie[temp].id1+1;
                if(trie[temp].pos==-1||(i-trie[temp].pos>=trie[temp].len))
                {
                    trie[temp].id2=trie[temp].id2+1;
                    trie[temp].pos=i;
                }
            }
            temp=trie[temp].fail;
        }
    }
}
int main()
{
    int n,choose,cas=1;
    char ss[10];
    while(scanf("%s",str)!=EOF)
    {
        scanf("%d",&n);
        trie[1].init();
        trie_s=1;
        for(int i=1;i<=n;i++)
        {
            scanf("%d %s",&choose,ss);
            put(ss,choose,i);
        }
        getFail();
        query(str);
        printf("Case %d\n",cas++);
        for(int i=1;i<=n;i++)
        {
            printf("%d\n",*x[i]);
        }
        printf("\n");
    }
    return 0;
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子空盼,更是在濱河造成了極大的恐慌丰涉,老刑警劉巖比勉,帶你破解...
    沈念sama閱讀 223,002評(píng)論 6 519
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件缚甩,死亡現(xiàn)場(chǎng)離奇詭異艺谆,居然都是意外死亡屎债,警方通過(guò)查閱死者的電腦和手機(jī)仅政,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,357評(píng)論 3 400
  • 文/潘曉璐 我一進(jìn)店門(mén),熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)扔茅,“玉大人已旧,你說(shuō)我怎么就攤上這事≌倌龋” “怎么了运褪?”我有些...
    開(kāi)封第一講書(shū)人閱讀 169,787評(píng)論 0 365
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)。 經(jīng)常有香客問(wèn)我秸讹,道長(zhǎng)檀咙,這世上最難降的妖魔是什么? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 60,237評(píng)論 1 300
  • 正文 為了忘掉前任璃诀,我火速辦了婚禮弧可,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘劣欢。我一直安慰自己棕诵,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,237評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布凿将。 她就那樣靜靜地躺著校套,像睡著了一般。 火紅的嫁衣襯著肌膚如雪牧抵。 梳的紋絲不亂的頭發(fā)上笛匙,一...
    開(kāi)封第一講書(shū)人閱讀 52,821評(píng)論 1 314
  • 那天,我揣著相機(jī)與錄音犀变,去河邊找鬼妹孙。 笑死,一個(gè)胖子當(dāng)著我的面吹牛获枝,可吹牛的內(nèi)容都是我干的蠢正。 我是一名探鬼主播,決...
    沈念sama閱讀 41,236評(píng)論 3 424
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼映琳,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼机隙!你這毒婦竟也來(lái)了蜘拉?” 一聲冷哼從身側(cè)響起萨西,我...
    開(kāi)封第一講書(shū)人閱讀 40,196評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎旭旭,沒(méi)想到半個(gè)月后谎脯,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,716評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡持寄,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,794評(píng)論 3 343
  • 正文 我和宋清朗相戀三年源梭,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片稍味。...
    茶點(diǎn)故事閱讀 40,928評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡废麻,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出模庐,到底是詐尸還是另有隱情烛愧,我是刑警寧澤,帶...
    沈念sama閱讀 36,583評(píng)論 5 351
  • 正文 年R本政府宣布,位于F島的核電站怜姿,受9級(jí)特大地震影響慎冤,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜沧卢,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,264評(píng)論 3 336
  • 文/蒙蒙 一蚁堤、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧但狭,春花似錦披诗、人聲如沸。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 32,755評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至息罗,卻和暖如春掂咒,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背迈喉。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,869評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工绍刮, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人挨摸。 一個(gè)月前我還...
    沈念sama閱讀 49,378評(píng)論 3 379
  • 正文 我出身青樓孩革,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親得运。 傳聞我的和親對(duì)象是個(gè)殘疾皇子膝蜈,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,937評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容

  • Spring Cloud為開(kāi)發(fā)人員提供了快速構(gòu)建分布式系統(tǒng)中一些常見(jiàn)模式的工具(例如配置管理,服務(wù)發(fā)現(xiàn)熔掺,斷路器饱搏,智...
    卡卡羅2017閱讀 134,720評(píng)論 18 139
  • 引言 字符串匹配一直是計(jì)算機(jī)科學(xué)領(lǐng)域研究和應(yīng)用的熱門(mén)領(lǐng)域,算法的改進(jìn)研究一直是一個(gè)十分困難的課題置逻。作為字符串匹配中...
    潮汐行者閱讀 1,655評(píng)論 2 6
  • 一推沸、字符串操作 strcpy(p, p1) 復(fù)制字符串 strncpy(p, p1, n) 復(fù)制指定長(zhǎng)度字符串 s...
    JaiUnChat閱讀 1,661評(píng)論 0 7
  • 9.19--9.23 第7章 正則表達(dá)式 正則表達(dá)式是一個(gè)拆分字符串并查詢(xún)相關(guān)信息的過(guò)程。 推薦練習(xí)網(wǎng)站: js ...
    如201608閱讀 1,039評(píng)論 0 4
  • 有感券坞。愛(ài)情的開(kāi)始并不是兩個(gè)人多么多么相配鬓催,最好的愛(ài)情,是一起慢慢地走過(guò)恨锚,一起進(jìn)步宇驾,一起成熟
    88497ef8823d閱讀 120評(píng)論 0 0