记录编号	338572	评测结果	AAAAAAAAAAAAAA
题目名称	隐藏口令	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.567 s
提交时间	2016-11-05 11:47:31	内存使用	80.35 MiB

#include <cstdio>
#include <cstring>
#include <cstdarg>
#include <string>
#include <algorithm>
#include <vector>
#include <list>
#include <queue>
#include <iostream>
using namespace std;
//最小表示法...
#define MAXN 200003
class SAM
{
public:
    int size, last;
    struct node
    {
        int len, link;
        int next[26];
        void init()
        {
            len = 0;
            link = -1;
            memset(next, 0, sizeof(next));
        }
    }st[MAXN<<2];
    int newst()
    {
        st[size++].init();
        return size-1;
    }
    SAM()
    {
        last = size = 0;
        newst();
    }
    void expand(int c)
    {
        int cur = newst();
        st[cur].len = st[last].len+1;
        int p;
        for(p = last; ~p && !st[p].next[c]; p = st[p].link)
            st[p].next[c] = cur;
        if(p == -1)
            st[cur].link = 0;
        else
        {
            int q = st[p].next[c];
            if(st[q].len == st[p].len + 1)
                st[cur].link = q;
            else
            {
                int clone = newst();
                st[clone].link = st[q].link;
                st[clone].len = st[p].len+1;
                memcpy(st[clone].next, st[q].next, sizeof(st[q].next));
                for(; ~p && st[p].next[c] == q; p = st[p].link)
                    st[p].next[c] = clone;
                st[q].link = st[cur].link = clone;
            }
        }
        last = cur;
    }
}sam;
char buf[200003<<1];
char note[200003<<1];
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <iostream>
using namespace std;
 
int *getNext(const char *s, int len)
{
    int *next = (int *)malloc(sizeof(int) * len + 16);
    next[0] = next[1] = 0;
    int j = 0;
    for(int i = 1; i < len; i++)
    {
        j = next[i];
        while(j && s[i] != s[j])j = next[j];
        next[i+1] = s[i] == s[j]? j+1:0;
    }
    return next;
}
int MP(const char *text, const char *pattern)
{
    int lt = strlen(text);
    int lp = strlen(pattern);
    int *next = getNext(pattern, lp);
    int ct = 0;
    int j = 0;
    for(int i = 0; i < lt; i++)
    {
        while(j && text[i] != pattern[j])j = next[j];
        if(text[i] == pattern[j])j++;
        if(j == lp)return i-lp+1;
    }
    free(next);
    return ct;
}
 
int main()
{
    freopen("hidden.in", "r", stdin);
    freopen("hidden.out", "w", stdout);
    int n;
    string s, _tmp;
    cin >> n;
    while(cin >> _tmp)s+=_tmp;
    
    int p = 0;
    for(int k = 0; k < 2; k++)
    for(int i = 0; i < n; i++)
    {
        sam.expand(s[i]-'a');
        buf[p++] = s[i];
    }
    buf[p] = 0;
    int t = 0;
    int c = 0;
    for(int i = 0; i < sam.size; i++)
    {
        for(int j = 0; j < 26; j++)
            if(sam.st[t].next[j])
            {
                note[c++] = 'a'+j;
                t = sam.st[t].next[j];
                break;
            }
        if(c == n)break;
    }
    note[c] = 0;
    printf("%d\n", MP(buf, note)%n);
    return 0;
}