BGC TRUST IUPC 2012

Problem A

Distinct Substring

Given a string S, Dexter wants to find the number of different substrings in S. He considers two substrings same if they have a cyclic permutation which is same.

If is a string of length n then it has n cyclic permutations and they are  for all . (Note that,  are non-existing).

For example, if T = “abcd” there are 4 cyclic permutations and they are: “abcd”, “bcda”, “cdab” and “dabc”.

So, string “aba”, “aab” and “baa” are all considered same. But “abc” and “bac” are different as there is no cyclic permutation of them which are same.

Input

First line contains an integer T (T <= 50) denoting the number of test cases. Each of the next T lines contains a string S which is composed of only lowercase latin letters. You can assume that the length of S is between 1 and 200 inclusive.

Output

For each test case, output the number of different substrings in a line.

Explanation: If S = “abcba” there are 10 cyclic different substrings and they are: “a”, “b”, “c”, “ab”, “bc”, “abc”, “bcb”, “cba”, “abcb” and “abcba”.

Problemsetter: Tasnim Imran Sunny

Special Thanks: Kazi Rakibul Hasan

將所有可能列舉出來 O(|S|^2)，再找到其最小表示法 O(|S|)，
然後使用雜湊或者是 set 去解決。
最後是 O(|S|^2)

#include <stdio.h>
#include <string.h>
#include <set>
#include <iostream>
using namespace std;
int MinExp(const char *s, const int slen) {
    int i = 0, j = 1, k = 0, x, y, tmp;
    while(i < slen && j < slen && k < slen) {
        x = i + k;
        y = j + k;
        if(x >= slen)    x -= slen;
        if(y >= slen)    y -= slen;
        if(s[x] == s[y]) {
            k++;
        } else if(s[x] > s[y]) {
            i = j+1 > i+k+1 ? j+1 : i+k+1;
            k = 0;
            tmp = i, i = j, j = tmp;
        } else {
            j = i+1 > j+k+1 ? i+1 : j+k+1;
            k = 0;
        }
    }
    return i;
}
int main() {
    int t;
    char s[1005], ss[1005];
    scanf("%d", &t);
    while(t--) {
        scanf("%s", s);
        int len = strlen(s);
        int i, j, k;
        set<string> S[205];
        for(i = 0; i < len; i++) {
            for(j = 0; i+j < len; j++) {
                //s[i...i+j]
                int pos = MinExp(s+i, j+1)+i;
                //puts("");
                for(k = 0; k <= j; k++) {
                    ss[k] = s[pos];
                    pos++;
                    if(pos == i+j+1)    pos = i;
                }
                ss[k] = '\0';
                S[k].insert(ss);
            }
        }
        int ret = 0;
        for(i = 0; i <= len; i++)
            ret += S[i].size();
        printf("%d\n", ret);
    }
    return 0;
}