LCA

POJ 3728 The merchant

Posted on

LCA 好题!

这道题我暂时只知道用Tarjan的解法。
Tarjan解法完美地运用了Tarjan的核心原理与性质:
深度优先搜索时的向下局部性。自己乱取得,蛤蛤蛤

题意:
给你一棵树,每个节点有一个权值。给你很多个询问,每个询问两个点。要你在给定点的树链上找到有序的最大差值。

思路:
首先考虑分治。设树链 u -> lca -> v
答案无非只有三种情况:

  1. u -> lca 的最大差值
  2. lca -> v 的最大差值
  3. lca -> v 的最大值 - u -> lca 的最小值

考虑dp维护这四个值。
因为运用Tarjan算法的时候,基于dfs,在你的眼里,当前节点就是向下整棵树的根节点,你完全不会去考虑往上的节点。
所以你现在使用的四个值,刚好是你当前节点的孩子节点的最优值。
基于这个事实,我们可以对其状态转移并维护。

AC Code

#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;

int n;
int val[maxn], res[maxn];
int up[maxn], down[maxn], max_val[maxn], min_val[maxn];
int root[maxn];
bool vis[maxn];

vector<int> g[maxn];
vector<pii> q[maxn];
vector<pii> ans[maxn];

int findRoot(int x)
{
    if (root[x] == x)
        return x;
    int fa = root[x];
    root[x] = findRoot(root[x]);
    up[x] = max(up[x], max(up[fa], max_val[fa] - min_val[x]));
    down[x] = max(down[x], max(down[fa], max_val[x] - min_val[fa]));
    max_val[x] = max(max_val[x], max_val[fa]);
    min_val[x] = min(min_val[x], min_val[fa]);
    return root[x];
}

void tarjan(int u)
{
    root[u] = u;
    vis[u] = true;
    int sz = q[u].size();
    for (int i = 0; i < sz; i++) {
        int v = q[u][i].second;
        if (vis[v]) {
            int lca = findRoot(v);
            ans[lca].push_back(make_pair(u, i));
        }
    }
    sz = g[u].size();
    for (int i = 0; i < sz; i++) {
        int v = g[u][i];
        if (!vis[v]) {
            tarjan(v);
            root[v] = u;
        }
    }
    sz = ans[u].size();
    for (int i = 0; i < sz; i++) {
        int x = ans[u][i].first, y = q[x][ans[u][i].second].second;
        int id = q[x][ans[u][i].second].first;
        if (id < 0) {
            id = -id;
            swap(x, y);
        }
        findRoot(x), findRoot(y);
        res[id] = max(up[y], down[x]);
        res[id] = max(res[id], max_val[x] - min_val[y]);
    }
}

void init()
{
    for (int i = 0; i <= n; i++) {
        g[i].clear(), q[i].clear(), ans[i].clear();
        vis[i] = false;
        up[i] = down[i] = 0;
    }
}

int main()
{
    int u, v, qnum;
    while (scanf("%d", &n) != EOF) {
        init();
        for (int i = 1; i <= n; i++) {
            scanf("%d", val + i);
            min_val[i] = max_val[i] = val[i];
        }
        for (int i = 1; i < n; i++) {
            scanf("%d %d", &u, &v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        scanf("%d", &qnum);
        for (int i = 1; i <= qnum; i++) {
            scanf("%d %d", &u, &v);
            q[u].push_back(make_pair(-i, v));
            q[v].push_back(make_pair(i, u));
        }
        tarjan(1);
        for (int i = 1; i <= qnum; i++)
            printf("%d\n", res[i]);
    }
    return 0;
}
最短路

POJ 2449 Remmarguts’ Date

Posted on

K短路裸题。

这里的K短路是基于每个点只能访问一次,也就是说这个K短路必须是一条链。
再换句话说,这个K短路的K是有限制的,如果超过了这个限制,就输出 -1 。
这是和之前多校的次短路不一样的地方。

简单说一下K短路的解决思路:
首先我们应该认识到,最最简单的最短路算法是基于 bfs 改进而来,我们用 bfs 的思路继续拓展,在第一次到达终点后并不停止,而是继续 bfs 搜索,直到第K次到达终点,就是我们要求的答案。
当然,单纯的 bfs 是瞎 jb 搜,堆优化的spfa效率良好,但我们可以更进一步优化。
K短路于此之上还用了 A* 优化,先对反图 最短路遍历一遍,在正图遍历的时候,除了对起点 src 到当前距离 堆优化以外,还对当前距离进行答案估计,并将其优先级先于距离。

仔细想一想,其实很显然,不过为什么最短路不用 A* 优化呢?
因为有处理估值函数的时间,最短路都已经求完了。

题意:
K短路裸题。

思路:
见上。

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 1e3 + 5;
const int maxm = 1e5 + 5;

int idx, n, m;
int src, des;
int head[maxn], head2[maxn];
bool inq[maxn];
int dis[maxn];

struct node {
    int to, weight;
    int next;
    node(int a = 0, int b = 0, int c = 0) { to = a, weight = b, next = c; }
    bool operator<(const node& a) const { return weight > a.weight; }
} edges[maxm], redges[maxm];

struct qnode {
    int node, dist, src_dis;
    bool operator<(const qnode& a) const { return dist == a.dist ? src_dis > a.src_dis : dist > a.dist; }
} tmp;

void addEdge(int u, int v, int w)
{
    edges[idx] = node(v, w, head[u]);
    head[u] = idx;
    redges[idx] = node(u, w, head2[v]);
    head2[v] = idx++;
}

void spfa(int st)
{
    queue<int> que;
    fill(dis, dis + 1 + n, inf);
    dis[st] = 0, inq[st] = true;
    que.push(st);
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        inq[u] = false;
        for (int id = head2[u]; ~id; id = redges[id].next) {
            int v = redges[id].to;
            if (dis[v] > dis[u] + redges[id].weight) {
                dis[v] = dis[u] + redges[id].weight;
                if (!inq[v]) {
                    inq[v] = true;
                    que.push(v);
                }
            }
        }
    }
}

void nthSP(int k)
{
    if (src == des)
        k++;
    priority_queue<qnode> que;
    que.push((qnode){ src, 0, 0 });
    int cnt = 0;
    while (!que.empty()) {
        tmp = que.top();
        que.pop();
        int u = tmp.node, dist = tmp.src_dis;
        if (u == des) {
            if (++cnt == k) {
                printf("%d\n", tmp.dist);
                return;
            }
        }
        for (int id = head[u]; ~id; id = edges[id].next)
            que.push((qnode){ edges[id].to, dist + edges[id].weight + dis[edges[id].to], dist + edges[id].weight });
    }
    puts("-1");
}

int main()
{
    int u, v, w, k;
    while (scanf("%d %d", &n, &m) != EOF) {
        memset(head, -1, sizeof head), idx = 0;
        memset(head2, -1, sizeof head2);
        while (m--) {
            scanf("%d %d %d", &u, &v, &w);
            addEdge(u, v, w);
        }
        scanf("%d %d %d", &src, &des, &k);
        spfa(des);
        nthSP(k);
    }
    return 0;
}
树形DP

CodeForces 842 C Ilya And The Tree

Posted on

树上的选择性DP……
不是很懂其他人的做法,偶然间看到有人用ruby A了,我也就用ruby敲了一蛤
速度有点玄……

题意:
给你一棵树,每个节点都有权值,要你求每个节点到根节点所形成的树链 gcd。
其中每条树链都可以选择一个节点使得权值变为 0 。

思路:
感觉这就是裸题……
只不过就是把数组改成树上了而已。
用一个栈或者队列去遍历这棵树,对于每个节点是否变0都考虑一下就好了……

AC Code

#!/usr/bin/env ruby
# encoding: utf-8
n = gets.to_i
a = gets.split.map(&:to_i)
g = Array.new(n) {[]}

(n-1).times do
    u, v = gets.split.map(&:to_i)
    u, v = u-1, v-1
    g[u] << v
    g[v] << u
end

def GCD(a, b) return b == 0 ? a : GCD(b, a%b) end

dp = Array.new(n) { Array.new(2) { [] } }
dp[0] = [[a[0]], [0]]
par = [-1]*n

st = [0]
until st.empty?
    u = st.pop
    g[u].each do |v|
        next if v == par[u]
        par[v] = u
        st.push(v)
        dp[v][0] += dp[u][0].map{|x| GCD(x,a[v])}
        dp[v][1] += dp[u][0]
        dp[v][1] += dp[u][1].map{|x| GCD(x,a[v]) }
        2.times do |i|
            dp[v][i].uniq!
        end
    end
end

print a[0]
for u in 1...n do
    print " #{dp[u][1].max}"
end
后缀数组

POJ 3693 Maximum repetition substring

Posted on

后缀数组之重复次数最多的连续重复子串
这道题真的是做的我脑壳疼……
口误,根本不能算是做,死嗑论文怎么也嗑不出来……

好难,这应该是我现在做过的后缀数组里最难的一题了……

这里放上我理解之后的思路:
首先枚举长度 l ,如果存在两个长度为 l 的连续重复子串,那么在 \( str[ 0 ] , str[ l ] , str[ l \times 2 ] \) …… 中必然会存在两个相邻的位置他们值相同(加上这个优化,速度可以大幅度提升),我们对这两个位置的后缀求最长公共前缀 lcp ,那么显然,由这两个位置得出的子串重复次数为 \( lcp \div l + 1 \)。
但是这个答案并不一定是正确的,因为我们只能确保 \( str[ 0 ] , str [ l ] , str[ l \times 2 ] \) …… 中会出现重复值,但是这几个是边界。
由kuangbin大佬给出一个想法是考虑 \( lcp \% l \) 的含义。\( lcp \% l \) 是代表着对于 某个长度为 l 的连续子串 s ,被截断在右侧的长度为 \( lcp \% l \) ,那么被截断在左侧的长度便是 \( l - lcp \% l \)。
那么这个子串 s 的实际左边界就是 我们枚举的 \( i - ( l - lcp \% l ) \) ,因此右侧为 \( i - ( l - lcp \% l ) + l \) 。由这个区间求出的 lcp 如果仍然大于等于 原先的 lcp ,那么就需要使得重复次数 + 1 。
然后我们根据最大重复次数记录每个可重复子串的长度。(因为我们要求的是重复次数最多,重复长度无关紧要)。
最后我们要求的是字典序最小的,所以我们只要根据后缀数组一一枚举判断即可。

题意:
求重复次数最多的连续重复子串,若有多个结果,输出字典序最小的那个。

思路:
见上。

AC Code

#include <algorithm>
#include <cstdio>
#include <cstring>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;

struct SuffixArray {
private:
    int len;
    int t1[maxn], t2[maxn], buc[maxn];
    int mmin[maxn][17], s[maxn];

    void DA(int n, int m)
    {
        int p, *x = t1, *y = t2;
        each(i, m) buc[i] = 0;
        each(i, n) buc[x[i] = s[i]]++;
        range(i, 1, m - 1) buc[i] += buc[i - 1];
        reach(i, n) sa[--buc[x[i]]] = i;
        for (int k = 1; k <= n; k <<= 1) {
            p = 0;
            range(i, n - k, n - 1) y[p++] = i;
            each(i, n) if (sa[i] >= k) y[p++] = sa[i] - k;
            each(i, m) buc[i] = 0;
            each(i, n) buc[x[i]]++;
            range(i, 1, m - 1) buc[i] += buc[i - 1];
            reach(i, n) sa[--buc[x[y[i]]]] = y[i];
            swap(x, y);
            p = 1, x[sa[0]] = 0;
            range(i, 1, n - 1) x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k] ? p - 1 : p++;
            if (p >= n)
                break;
            m = p;
        }
    }

    void getHeight(int n)
    {
        int j, k = 0;
        each(i, n + 1) rank[sa[i]] = i;
        each(i, n)
        {
            k ? k-- : 0;
            j = sa[rank[i] - 1];
            while (s[i + k] == s[j + k])
                k++;
            height[rank[i]] = k;
        }
    }

public:
    int sa[maxn];
    int rank[maxn], height[maxn];

    void input(char* str)
    {
        len = strlen(str);
        range(i, 0, len - 1) s[i] = str[i] - 'a' + 1;
        s[len] = 0;
        DA(len + 1, 28);
        getHeight(len);
    }

    void initRMQ()
    {
        for (int i = 1; i <= len; i++)
            mmin[i][0] = height[i];
        for (int j = 1; (1 << j) <= len; j++)
            for (int i = 1; i + (1 << j) - 1 <= len; i++)
                mmin[i][j] = min(mmin[i][j - 1], mmin[i + (1 << (j - 1))][j - 1]);
    }

    int RMQ(int l, int r)
    {
        int k = 0;
        while ((1 << (k + 1)) <= r - l + 1)
            k++;
        return min(mmin[l][k], mmin[r - (1 << k) + 1][k]);
    }

    int lcp(int a, int l)
    {
        if (a == l)
            return len - a;
        int u = rank[a], v = rank[l];
        return u > v ? RMQ(v + 1, u) : RMQ(u + 1, v);
    }

    int ans[maxn];
    void work(char* str, int cas)
    {
        int maxx = 0, cnt = 0;
        range(l, 1, len - 1) for (int i = 0; i + l < len; i += l)
        {
            if (str[i] != str[i + l])
                continue;
            int k = lcp(i, i + l), num = k / l + 1;
            int pre = i - (l - k % l);
            if (pre >= 0 && k % l) {
                if (lcp(pre, pre + l) >= k)
                    num++;
            }
            if (num > maxx) {
                maxx = num;
                cnt = 0;
                ans[cnt++] = l;
            } else if (num == maxx)
                ans[cnt++] = l;
        }
        cnt = unique(ans, ans + cnt) - ans;
        int key = -1, st = 0;
        range(i, 1, len)
        {
            each(j, cnt) if (lcp(sa[i], sa[i] + ans[j]) >= (maxx - 1) * ans[j])
            {
                key = ans[j];
                st = sa[i];
                break;
            }
            if (~key)
                break;
        }
        str[st + key * maxx] = '\0';
        printf("Case %d: %s\n", cas, str + st);
    }

} suffix_array;

char buf[maxn];

int main()
{
    int cas = 0;
    while (scanf("%s", buf) != EOF && buf[0] != '#') {
        suffix_array.input(buf);
        suffix_array.initRMQ();
        suffix_array.work(buf, ++cas);
    }
    return 0;
}
后缀数组

POJ 3261 Milk Patterns

Posted on

后缀数组之可重叠 k 次最长重复子串。
数据好水……他的 “ 字符 ” 范围为 \( [ 0 , 1e6 ] \)
按我最开始的想法,求后缀数组的时候,在字符最大值超过 char 我就打算用 sort 代替基数排序了。
然而……直接取最大值用基数排序居然过了,还是 63 ms ……

下面是可重叠 k 次最长重复子串的求法:
解法与不可重叠最长重复子串的做法基本一致。
二分答案,将排序后的后缀按照二分值分成若干组,如果某一组的数量大于等于 k ,那么这个二分值是可行值。

题意:
可重叠 k 次最长重复子串。

思路:
见上。

AC Code

#include <algorithm>
#include <cstdio>
#include <cstring>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
typedef long long ll;
const int maxn = 2e4 + 10;

struct SuffixArray {
private:
    int len;
    int t1[maxn], t2[maxn], buc[maxn];
    int s[maxn];

    void DA(int n, int m)
    {
        int p, *x = t1, *y = t2;
        each(i, m) buc[i] = 0;
        each(i, n) buc[x[i] = s[i]]++;
        range(i, 1, m - 1) buc[i] += buc[i - 1];
        reach(i, n) sa[--buc[x[i]]] = i;
        for (int k = 1; k <= n; k <<= 1) {
            p = 0;
            range(i, n - k, n - 1) y[p++] = i;
            each(i, n) if (sa[i] >= k) y[p++] = sa[i] - k;
            each(i, m) buc[i] = 0;
            each(i, n) buc[x[i]]++;
            range(i, 1, m - 1) buc[i] += buc[i - 1];
            reach(i, n) sa[--buc[x[y[i]]]] = y[i];
            swap(x, y);
            p = 1, x[sa[0]] = 0;
            range(i, 1, n - 1) x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k] ? p - 1 : p++;
            if (p >= n)
                break;
            m = p;
        }
    }

    void getHeight(int n)
    {
        int j, k = 0;
        each(i, n + 1) rank[sa[i]] = i;
        each(i, n)
        {
            k ? k-- : 0;
            j = sa[rank[i] - 1];
            while (s[i + k] == s[j + k])
                k++;
            height[rank[i]] = k;
        }
    }

public:
    int sa[maxn];
    int rank[maxn], height[maxn];

    void input(int n)
    {
        len = n;
        int maxx = 0;
        each(i, n)
        {
            scanf("%d", s + i);
            maxx = max(maxx, s[i]);
        }
        s[len] = 0;
        DA(len + 1, maxx + 1);
        getHeight(len);
    }

    bool check(int key, int k)
    {
        int cnt = 1;
        range(i, 2, len) if (height[i] >= key)
        {
            if (++cnt >= k)
                return true;
        }
        else cnt = 1;
        return cnt >= k;
    }

} suffix_array;

int main()
{
    int n, k;
    while (scanf("%d %d", &n, &k) != EOF) {
        suffix_array.input(n);
        int l = 0, r = n, mid;
        while (l <= r) {
            mid = (l + r) >> 1;
            if (suffix_array.check(mid, k))
                l = mid + 1;
            else
                r = mid - 1;
        }
        printf("%d\n", l - 1);
    }
    return 0;
}
后缀数组

HDU 4691 Front compression

Posted on

后缀数组之最长公共前缀的不定查询。
因为查询很多,所以要结合RMQ算法。这个也是很简单的,一般不会有什么变化,只要套一下木板就好了。

但是这个有一个非常困扰我的地方,就是题目给定的查询不是后缀之间的最长公共前缀查询,而是子串之间的查询,这可难倒我了,我也不知道该如何解决。

看了题解后,发现其实解决方法很简单,只要将求得的 LCP 与两个子串长度互相比较,三个长度取最小就是我们要得答案。

题意:
给你一个字符串,再给你很多子串,要你将所有给定的子串进行压缩。
压缩方式为将两个字符串的最长公共前缀在第二个字符串用数字表示。

输出未压缩的长度和压缩后的长度,要记空格和换行。

思路:
不断求 LCP 即可。
在求的过程中有几个注意的地方。

  • 注意后缀相同的情况。
  • 得到两个后缀的 rank 后不能直接使用 RMQ ,一方面有不确定的大小关系,另一方面,我们是对height 数组求 RMQ ,做区间应为 较小的 rank + 1 。
  • 注意将RMQ数组开大……

这道题使用的代码已经能成为我求 LCP 的模板了 除了改成DC3

AC Code

#include <bits/stdc++.h>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;

struct SuffixArray {
private:
    int len;
    int t1[maxn], t2[maxn], buc[maxn];
    int mmin[maxn][17], s[maxn];

    void DA(int n, int m) 
    {
        int p, *x = t1, *y = t2;
        each(i, m) buc[i] = 0;
        each(i, n) buc[x[i] = s[i]]++;
        range(i, 1, m - 1) buc[i] += buc[i - 1];
        reach(i, n) sa[--buc[x[i]]] = i;
        for (int k = 1; k <= n; k <<= 1) {
            p = 0;
            range(i, n - k, n - 1) y[p++] = i;
            each(i, n) if (sa[i] >= k) y[p++] = sa[i] - k;
            each(i, m) buc[i] = 0;
            each(i, n) buc[x[i]]++;
            range(i, 1, m - 1) buc[i] += buc[i - 1];
            reach(i, n) sa[--buc[x[y[i]]]] = y[i];
            swap(x, y);
            p = 1, x[sa[0]] = 0;
            range(i, 1, n - 1) x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k] ? p - 1 : p++;
            if (p >= n)
                break;
            m = p;
        }
    }

    void getHeight(int n) 
    {
        int j, k = 0;
        each(i, n + 1) rank[sa[i]] = i;
        each(i, n)
        {
            k ? k-- : 0;
            j = sa[rank[i] - 1];
            while (s[i + k] == s[j + k])
                k++;
            height[rank[i]] = k;
        }
    }

public:
    int sa[maxn];
    int rank[maxn], height[maxn];

    void input(char* str)
    {
        len = strlen(str);
        range(i, 0, len) s[i] = str[i];
        DA(len + 1, 128);
        getHeight(len);
    }

    void initRMQ()
    {
        for (int i = 1; i <= len; i++)
            mmin[i][0] = height[i];
        for (int j = 1; (1 << j) <= len; j++)
            for (int i = 1; i + (1 << j) - 1 <= len; i++)
                mmin[i][j] = min(mmin[i][j - 1], mmin[i + (1 << (j - 1))][j - 1]);
    }

    int RMQ(int l, int r)
    {
        int k = 0;
        while ((1 << (k + 1)) <= r - l + 1)
            k++;
        return min(mmin[l][k], mmin[r - (1 << k) + 1][k]);
    }

    int lcp(int a, int l)
    {
        if (a == l)
            return len - a;
        int u = rank[a], v = rank[l];
        return u > v ? RMQ(v + 1, u) : RMQ(u + 1, v);
    }

} suffix_array;

char str[maxn];

int calc(int val)
{
    int ret = 1;
    while (val > 9) {
        val /= 10;
        ret++;
    }
    return ret;
}

int main()
{
    int qn, pl, pr, l, r;
    while (scanf("%s", str) != EOF) {
        suffix_array.input(str);
        suffix_array.initRMQ();
        scanf("%d %d %d", &qn, &pl, &pr);
        ll lans = pr - pl + 1, rans = pr - pl + 3;
        qn--;
        while (qn--) {
            scanf("%d %d", &l, &r);
            int lcp = suffix_array.lcp(pl, l);
            lcp = min(lcp, min(pr - pl, r - l));
            lans += r - l + 1;
            rans += r - l + 2 - lcp + calc(lcp);
            pl = l, pr = r;
        }
        printf("%lld %lld\n", lans, rans);
    }
    return 0;
}
后缀数组

HDU 4552 怪盗基德的挑战书

Posted on

一道不知所以然的题目……

没什么好废话的,直接上题解。

题意:
要你求一个字符串的所有前缀在自己本身的所有出现次数。

思路:
这道题如果用KMP的话是十分简单的,但是我一开始没想到用KMP,想了一些时间,看了kuangbin的博客说可以用KMP求解,略想了一下,果真如此。

KMP思路:
直接next数组跳几下就可以了。

后缀数组思路:
后缀数组的思路让我有点蒙逼……只要将所有后缀与最长的后缀,也就是原串的最长公共前缀相加再加上原串长度就是答案。
而看过论文的都应该知道,这个是可以\( O( n ) \)直接求出来的。
但是还是有点似董非董。

#include <bits/stdc++.h>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

const int maxn = 1e5 + 5;
int sa[maxn];
int t1[maxn], t2[maxn], buc[maxn];
int rnk[maxn], height[maxn];

void buildSA(int s[], int n, int m) //n取字符串长度+1 m为字符中的上界 一般为 128
{ 
    int p, *x = t1, *y = t2;
    each(i, m) buc[i] = 0;
    each(i, n) buc[x[i] = s[i]]++;
    range(i, 1, m - 1) buc[i] += buc[i - 1];
    reach(i, n) sa[--buc[x[i]]] = i;
    for (int k = 1; k <= n; k <<= 1) {
        p = 0;
        range(i, n - k, n - 1) y[p++] = i;
        each(i, n) if (sa[i] >= k) y[p++] = sa[i] - k;
        each(i, m) buc[i] = 0;
        each(i, n) buc[x[i]]++;
        range(i, 1, m - 1) buc[i] += buc[i - 1];
        reach(i, n) sa[--buc[x[y[i]]]] = y[i];
        swap(x, y);
        p = 1, x[sa[0]] = 0;
        range(i, 1, n - 1) x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k] ? p - 1 : p++;
        if (p >= n)
            break;
        m = p;
    }
}

void getHeight(int s[], int n) //n为字符串长度
{
    int j, k = 0;
    each(i, n + 1) rnk[sa[i]] = i;
    each(i, n)
    {
        k ? k-- : 0;
        j = sa[rnk[i] - 1];
        while (s[i + k] == s[j + k])
            k++;
        height[rnk[i]] = k;
    }
}

char str[maxn];
int s[maxn];

int main()
{
    while (scanf("%s", str) != EOF) {
        int len = strlen(str);
        range(i, 0, len) s[i] = str[i];
        buildSA(s, len + 1, 128);
        getHeight(s, len);
        int t = rnk[0], ans = len, tmp = len;
        while (t > 1) {
            tmp = min(tmp, height[t--]);
            ans += tmp;
        }
        t = rnk[0] + 1, tmp = len;
        while (t <= len) {
            tmp = min(tmp, height[t++]);
            ans += tmp;
        }
        printf("%d\n", ans % 256);
    }
    return 0;
}