Posted 09/08/2015Updated 07/19/2023 Semprathlon / Simfae Dean ACM-ICPC / Programing2 minutes read (About 225 words)

hdu 2203 亲和串 KMP

亲和串

/** Sep 8, 2015 10:56:55 PM
 * PrjName:hdu2203
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        InputReader in=new InputReader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        while(in.nextLine()!=null){
            String s=in.next();
            s=new String(s+s);
            String t=in.next();
            out.println(KMP.Index(s, t)>-1?"yes":"no");
        }
        out.flush();
        out.close();
    }

}
class KMP{
    static int next[];
    static void getNext(String T){
        next=new int[T.length()+1];
        int j = 0, k = -1; next[0] = -1;
        while(j < T.length())
            if(k == -1 || T.charAt(j) == T.charAt(k))
                next[++j] = ++k;
            else
                k = next[k];
    }
    static int Index(String S,String T)
    {
        int i = 0, j = 0;
        getNext(T);
        
        for(i = 0; i < S.length()&&j<T.length(); i++)
        {
            while(j > 0 && S.charAt(i) != T.charAt(j))
                j = next[j];
            if(S.charAt(i) == T.charAt(j))
                j++;
        }
        if(j == T.length())
            return i - T.length();
        else
            return -1;
    }
    static int Count(String S,String T)
    {
        int res = 0,j=0;
        if(S.length() == 1 && T.length() == 1)
        {
            if(S.charAt(0) == T.charAt(0))
                return 1;
            else
                return 0;
        }
        getNext(T);
        for(int i = 0; i < S.length(); i++)
        {
            while(j > 0 && S.charAt(i) != T.charAt(j))
                j = next[j];
            if(S.charAt(i) == T.charAt(j))
                j++;
            if(j == T.length())
            {
                res++;
                j = next[j];
            }
        }
        return res;
    }
}

Posted 09/08/2015Updated 07/19/2023 Semprathlon / Simfae Dean ACM-ICPC / Programing2 minutes read (About 299 words)

hdu 2222 Keywords Search AC自动机

Keywords Search

/** Sep 8, 2015 8:34:27 PM
 * PrjName:hdu2222
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;

public class Main {

    /**
     * @param args
     */
    static AC ac = new AC();

    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int T = in.nextInt();
        while (T-- > 0) {
            int n = in.nextInt();
            ac.clear();
            for (int i = 1; i <= n; i++)
                ac.insert(in.next());
            ac.build();
            out.println(ac.query(in.next()));
        }
        out.flush();
        out.close();
    }

}

class AC {
    final int maxl = 500010, maxc = 26;
    final char fstc = 'a';
    int root, L;
    int[][] next;
    int[] fail, end;
    Queue<Integer> que = new LinkedList<Integer>();

    AC() {
        next = new int[maxl][maxc];
        fail = new int[maxl];
        end = new int[maxl];
        L = 0;
        root = newnode();
    }

    void clear() {
        Arrays.fill(fail, 0);
        Arrays.fill(end, 0);
        L = 0;
        root = newnode();
    }

    int newnode() {
        Arrays.fill(next[L], -1);
        end[L++] = 0;
        return L - 1;
    }

    void insert(String str) {
        int now = root;
        for (int i=0;i<str.length();i++) {
            char ch=str.charAt(i);
            if (next[now][ch - fstc] == -1)
                next[now][ch - fstc] = newnode();
            now = next[now][ch - fstc];
        }
        end[now]++;
    }

    void build() {
        que.clear();
        fail[root] = root;
        for (int i = 0; i < maxc; i++)
            if (next[root][i] == -1)
                next[root][i] = root;
            else {
                fail[next[root][i]] = root;
                que.add(next[root][i]);
            }
        while (!que.isEmpty()) {
            int now = que.poll();
            for (int i = 0; i < maxc; i++)
                if (next[now][i] == -1)
                    next[now][i] = next[fail[now]][i];
                else {
                    fail[next[now][i]] = next[fail[now]][i];
                    que.add(next[now][i]);
                }
        }
    }

    int query(String str) {
        int now = root, res = 0;
        for (int i=0;i<str.length();i++) {
            char ch=str.charAt(i);
            now = next[now][ch - fstc];
            int tmp = now;
            while (tmp != root) {
                res += end[tmp];
                 end[tmp] = 0;
                tmp = fail[tmp];
            }
        }
        return res;
    }
}

Posted 07/26/2015Updated 07/19/2023 Semprathlon / Simfae Dean ACM-ICPC / Programing2 minutes read (About 239 words)

BestCoder 1st Anniversary T_T

1001 Souvenir

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)

/**
 * 2015年7月25日 下午7:07:41
 * PrjName:0725-01
 * @ Semprathlon
 */
public class Main {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        InputReader in=new InputReader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        int T=in.nextInt();
        while(T-->0){
            int n=in.nextInt();
            int m=in.nextInt();
            int p=in.nextInt();
            int q=in.nextInt();
            int ans=0,has=0;
            if (m*p>q)
                ans+=n/m*q;
            else ans+=n/m*m*p;
            ans+=n%m*p;
            if ((n+m)/m*q<ans) ans=(n+m)/m*q;
            out.println(ans);
        }
        out.flush();
        out.close();
    }

}

1002 Hidden String

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
用Trie做查询时，往死胡同里钻而且根本停不下来，啊啊啊啊……

#include <cstdio>
#include <cstring>
char s[200], con[] = "anniversary";

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%s", s);
        int len = strlen(s);
        bool flag = false;
        for(int i = 0; i <= 8; i++)
        {
            for(int j = i + 1; j <= 9; j++)
            {
                int k = 0;
                while(k < len && strncmp(con, s + k, i + 1) != 0)
                    k ++;
                if(k == len) 
                    continue;
                k += i + 1;
                while(k < len && strncmp(con + i + 1, s + k, j - i) != 0)
                    k ++;
                if(k == len) 
                    continue;
                k += j - i;
                while(k < len && strncmp(con + j + 1, s + k, 10 - j) != 0)
                    k ++;
                if(k != len)
                {
                    flag = true;
                    break;
                }
            }
        }
        if(flag) 
            puts("YES");
        else 
            puts("NO");
    }
}

这里的枚举倒是简洁得出奇。

1003 Sequence

Time Limit: 2000/2000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
下意识地做了贪心，果然被hack

Posted 05/17/2015Updated 07/19/2023 Semprathlon / Simfae Dean ACM-ICPC / Programing3 minutes read (About 504 words)

hdu 4821 String hash乱搞

String

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Problem Description

Given a string S and two integers L and M, we consider a substring of S as “recoverable” if and only if
(i) It is of length M*L;
(ii) It can be constructed by concatenating M “diversified” substrings of S, where each of these substrings has length L; two strings are considered as “diversified” if they don’t have the same character for every position.

Two substrings of S are considered as “different” if they are cut from different part of S. For example, string “aa” has 3 different substrings “aa”, “a” and “a”.

Your task is to calculate the number of different “recoverable” substrings of S.

Input

The input contains multiple test cases, proceeding to the End of File.

The first line of each test case has two space-separated integers M and L.

The second ine of each test case has a string S, which consists of only lowercase letters.

The length of S is not larger than 10^5, and 1 ≤ M * L ≤ the length of S.

Output

For each test case, output the answer in a single line.

Sample Input

3 3
abcabcbcaabc

Sample Output

Source

2013 Asia Regional Changchun

纯粹是寻找一个最佳的hash姿势？而且还要懂得合适的时间优化？
真的TLE了好几次，现场赛的难点
枚举字串起点不必从头找到尾，因为向后滚的操作涵盖了i>=l以后的字串

#include<cstdio>
#include<cstring>
#include<memory.h>
#include<string>
#include<map>
#define CLEAR(a) memset((a),0,sizeof((a)))

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
const int maxn=1e5+10;
const ULL base=29;//prime

map<ULL,int> mp;

ULL nbase[maxn],ha[maxn];
char str[maxn];
//string s;

void init()
{
    nbase[0]=1;
    for(int i=1;i<maxn;i++) nbase[i]=nbase[i-1]*base;
}

inline ULL Hash(char *s,int len,ULL *_hash)  //按各个后缀hash
{
    _hash[len]=0;
    for(int i=len-1;i>=0;i--)
        _hash[i]=_hash[i+1]*base+s[i]-'a';
}

inline ULL Get(ULL *_hash,int pos,int len)
{
    return _hash[pos]-_hash[pos+len]*nbase[len];
}

int main()
{
    init();
    int m,l;

    while(~scanf("%d%d",&m,&l))
    {
        LL ans=0;
        scanf("%s",str);
        int len=strlen(str);
        Hash(str,len,ha);
        for(int i=0;i<=len-m*l&&i<l;i++) //此处不加条件i<l就TLE
        {
            mp.clear();
            for(int j=i;j<i+m*l;j+=l)
            {
                ULL h=Get(ha,j,l);
                //cout<<h<<':'<<s.substr(j,l)<<endl;
                mp[h]++;
            }
            if (mp.size()==m) ans++;
            for(int j=i+m*l;j<=len-l;j+=l)
            {
                ULL h=Get(ha,j-m*l,l);
                //cout<<h<<':'<<s.substr(j-m*l,l)<<endl;
                mp[h]--;
                if (!mp[h]) mp.erase(h);
                h=Get(ha,j,l);
                //cout<<h<<':'<<s.substr(j,l)<<endl;
                mp[h]++;
                if (mp.size()==m) ans++;
            }
        }
        printf("%I64d\n",ans);
    }
    return 0;
}