Topic link :【http://www.lydsy.com/JudgeOnline/problem.php?id=3172】

The question : Give all the words in an article , Then find out how many times each word appears in the passage , Words are separated by punctuation .

Answer key : It's time , The simple way is , First in AC Insert words into the automaton , And write down every word , Then use each word to maintain the answer . But this is not allowed in time and space , Only maintain answers when inserting . This is the process , At the time of insertion , Each passing point , Add one to the value of this node , Record the position at the end of the word at the same time , And then I'm trying to play Fail When , Just walk backwards .

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2024 * 1024 + 15;
char tmp[maxn];
struct Aho_C
{
int Next[maxn][26], Fail[maxn], pos[maxn], cnt[maxn];
int que[maxn], st, ed;
int root, sz;
int newnode()
{
for(int i = 0; i < 26; i++) Next[sz][i] = 0;
cnt[sz] = 0;
sz++;
return sz - 1 ;
}
void init()
{
sz = 0;
root = newnode();
}
void Insert(char buf[], int id)
{
int len = strlen(buf);
int now = root;
for(int i = 0; i < len; i++)
{
if(!Next[now][buf[i] - 'a'])
Next[now][buf[i] - 'a'] = newnode();
now = Next[now][buf[i] - 'a'];
cnt[now]++;
}
pos[id] = now;
}
void getFail()
{
st = ed = 1;
for(int i = 0; i < 26; i++)
if(Next[root][i])
que[ed++] = Next[root][i];
while(st != ed)
{
int u = que[st++];
for(int i = 0; i < 26; i++)
{
int &v = Next[u][i];
if(!v)
{
v = Next[Fail[u]][i];
continue;
}
Fail[v] = Next[Fail[u]][i];
que[ed++] = v;
}
}
for(int i = ed - 1; i >= 1; i--) cnt[Fail[que[i]]] += cnt[que[i]];
}
} ac;
int main()
{
int N;
scanf("%d", &N);
ac.init();
for(int i = 1; i <= N; i++)
{
scanf("%s", tmp);
ac.Insert(tmp, i);
}
ac.getFail();
for(int i = 1; i <= N; i++) printf("%d\n", ac.cnt[ac.pos[i]]);
return 0;
}

BZOJ 3172 [Tjoi2013] word AC automata Fail More about trees

  1. BZOJ 3172: [Tjoi2013] word [AC automata Fail Trees ]

    3172: [Tjoi2013] word Time Limit: 10 Sec  Memory Limit: 512 MBSubmit: 3198  Solved: 1532[Submit][Status ...

  2. bzoj 3172: [Tjoi2013] word AC automata

    3172: [Tjoi2013] word Time Limit: 20 Sec  Memory Limit: 256 MB Topic linking http://www.lydsy.com/JudgeOnline/pr ...

  3. BZOJ 2905: recite words AC automata +fail Trees +dfs order + Line segment tree

    Description Given a sheet containing N A list of words , Every word has a value W. It is required to select a subsequence from which each word is a substring of the next word , In the maximal subsequence W And . Input The first line is an integer TEST, Represents a data group ...

  4. BZOJ3172[Tjoi2013] word ——AC automata (fail Trees )

    Title Description Someone reads a paper , A paper is made up of many words . But he found that a word would appear many times in a paper , Now I want to know how many times each word appears in the paper . Input The first integer N, How many words are there , Next N Lines, one word per line . Every ...

  5. BZOJ 3172 [Tjoi2013] word AC Self driving machine (fail Trees )

    The question : link Method :AC Own the main engine and fail The nature of the tree analysis : review AC The first question of self driving machine ?( The real first question is that I wrote it all over again hdu2222! ) To tell you the truth, it looks like a sb topic , Just build your own drive . ...

  6. BZOJ2905: recite words AC automata +fail Trees + Line segment tree

    $zjq$ God saw at a glance that $AC$ automata $Orz$ Let's just talk about the practice First, for each string, build $AC$ automata take $fail$ Tree find Then find out $dfs$ order We found a word $S_i$ yes $S_j$ If and only if $S ...

  7. bzoj 3172 [Tjoi2013] word (fail Trees ,DP)

    [ Topic link ] http://www.lydsy.com/JudgeOnline/problem.php?id=3172 [ The question ] The meaning of the title is like this , Give me a few words , Find the number of times each word appears in this pile of words . ...

  8. 【 Learning notes 】ac automata &amp;fail Trees

    Definition Solve the problem of text string and multiple pattern string matching : Its essence is a dictionary tree formed by multiple pattern strings , from tie I know the meaning of :trie Each node on the is prefixed with a pattern string : stay trie Add on fail edge , A node fail The edge points to this section ...

  9. BZOJ 3172([Tjoi2013] word - Suffix array first question +RMQ)

    3172: [Tjoi2013] word Time Limit: 10 Sec   Memory Limit: 512 MB Submit: 268   Solved: 145 [ Submit][ St ...

Random recommendation

  1. Linux And HTTP service ,APACHE

    1. Basic knowledge of HTTP: Hypertext transfer protocol , Hyperlinks URI:Uniform Resource Identifier, Globally unique name character MIME:Multipurpose Internet Mail Ext ...

  2. Use EXECUTE IMMEDIATE To generate SQL

    One SQL, adopt SPM Fix its execution plan , Can pass DBMS_SPM.LOAD_PLANS_FROM_CURSOR_CACHE Realization . You can also use this function without modifying the original SQL In this case, add HINT To fix the execution plan .D ...

  3. MVC Use entity framework Access database Release IIS

    1.  SQL SERVER Database content 2. MVC engineering 3. EF Reference resources Engineering structure : Corresponding entity class : public class MvcUser { public int Id { get; set; ...

  4. 【Cocos2d-x】 Screenshot sharing function

    Cocos2d-x Screenshot implementation The picture will be saved in data/data/ Package name /files Under the folder . Android Next share a picture linux File permissions under the system In general android Each application under is a separate ...

  5. css3 Make a beautiful button

    aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAFMAAAA4CAIAAAAO41POAAAGWklEQVRogeWabWwTdRzH/8EwMb6Q69

  6. javaIO Stream to read and write txt file

    javaIO Stream to read and write files File is written to : InputStreamReader BufferedReader File read : FileOutputStream package javatest.basic22 ...

  7. turn :iOS Program main What happened before the function

    Original address :http://blog.sunnyxx.com/2014/08/30/objc-pre-main/ I'm the foreword One iOS app Of main() Function in main.m in , This is what we know as a program portal . ...

  8. static state TLS And dynamic TLS

    static state TLS How to use : #include <Windows.h> #include <iostream> #include <iomanip> using name ...

  9. Windows Refresh DNS cache

    Release IP Configuration information ipconfig /release Refresh DNS ipconfig /flushdns Update NIC adapter ipconfig /renew

  10. rpm database

    rpm database /var/lib/rpm