月份：2016年11月

REPORT HIHOCODER1353-满减优惠

REPORT HIHOCODER1353-满减优惠

http://hihocoder.com/problemset/problem/1353
==========================================================================

DP应该也是可以的
==========================================================================

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace HIHOCODER1353
{
class Program
{
static void Main(string[] args)
{
string[] inp;
int n = Convert.ToInt32(inp[0]);
int m = Convert.ToInt32(inp[1]);
int[] price = new int[n];
int totalvalue = 0;
for (int i = 0; i < n; i++)
{
price[i] = Convert.ToInt32(inp[i]);
totalvalue += price[i];
}
if (totalvalue < m)
{
Console.WriteLine(-1);
return;
}
FIND f = new HIHOCODER1353.FIND(price, n, m);
Console.WriteLine(f.ANS);
}
}
class FIND
{
int[] value;
int N, M;
int CUR = 0;
int MAX, SUM;
public int ANS;
public FIND(int[] v, int n, int m)
{
value = new int[n];
v.CopyTo(value, 0);
N = n;
M = m;
MAX = int.MaxValue;
SUM = value.Sum();

int max = 1 << N;
for (int i = 1; i <= max; i++)
{
CUR = 0;
for (int j = 0; j < N; j++)
{
if (((1 << j) & i) != 0)
{
CUR += value[j];
}
if (CUR > SUM)
{
break;
}
if (CUR >= M && CUR <= MAX)
{
MAX = CUR;
break;
}
}
}
ANS = MAX;
}
}
}


HIHOCODER-WEEK125 GeoHash编解码

HIHOCODER-WEEK125 GeoHash编解码

WEEK124我选择鸽了……

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace GeoHash
{
class Program
{
static void Main(string[] args)
{
int N = Convert.ToInt32(inp[0]);
int M = Convert.ToInt32(inp[1]);
for (int i = 0; i < N; ++i)
{
decimal A = Convert.ToDecimal(inp[0]);
decimal B = Convert.ToDecimal(inp[1]);
GeoHash geohash = new GeoHash();
Console.WriteLine(geohash.Encode(A, B, 10));
}
for (int i = 0; i < M; ++i)
{
GeoHash geohash = new GeoHash();
decimal[] red = geohash.DeCode(inpt);
Console.WriteLine("{0} {1}", red[0].ToString("f6"), red[1].ToString("f6"));
}
}
}
class GeoHash
{
private List<char> Base32Coding;
public GeoHash()
{
Base32Coding = new List<char> { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'm', 'n', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' };
}
public string Encode(decimal latitude, decimal longitude, int precision)
{
decimal latitudeLeft = -90, latitudeRight = 90;
decimal longitudeLeft = -180, longitudeRight = 180;
int length = precision * 5;
string hash = "";
int bits = 0;
for (int i = 1; i <= length; ++i)
{
if (i % 2 == 0)
{
decimal mid = (latitudeLeft + latitudeRight) / 2;
if (latitude > mid)
{
bits = bits * 2 + 1;
latitudeLeft = mid;
}
else
{
bits = bits * 2;
latitudeRight = mid;
}
}
else
{
decimal mid = (longitudeLeft + longitudeRight) / 2;
if (longitude > mid)
{
bits = bits * 2 + 1;
longitudeLeft = mid;
}
else
{
bits = bits * 2;
longitudeRight = mid;
}
}
if (i % 5 == 0)
{
hash += Base32Coding[bits];
bits = 0;
}
}
return hash;
}
public decimal[] DeCode(string hash)
{
bool odd = true;
decimal latitudeLeft = -90, latitudeRight = 90;
decimal longitudeLeft = -180, longitudeRight = 180;
int length = hash.Length;
for (int i = 0; i < length; ++i)
{
char currentcode = hash[i];
int bits = Base32Coding.IndexOf(currentcode);
for (int j = 4; j >= 0; --j)
{
int bit = (bits >> j) & 1;
if (odd)
{
decimal mid = (longitudeLeft + longitudeRight) / 2m;
if (1 - bit == 0)
longitudeLeft = mid;
else longitudeRight = mid;
}
else
{
decimal mid = (latitudeLeft + latitudeRight) / 2m;
if (1 - bit == 0)
latitudeLeft = mid;
else latitudeRight = mid;
}
odd = !odd;
}
}
decimal[] ret = new decimal[2];
ret[0] = (latitudeLeft + latitudeRight) / 2;
ret[1] = (longitudeLeft + longitudeRight) / 2;
return ret;
}
}
}


REPORT-The 2016 ACM-ICPC Asia Beijing Regional Contest Problem D. What a Beautiful Lake

REPORT-The 2016 ACM-ICPC Asia Beijing Regional Contest Problem D. What a Beautiful Lake

Problem D. What a Beautiful Lake
Description
Weiming Lake, also named “Un-named Lake”, is the most famous scenic spot in Peking University. It is located in the north of the campus and is surrounded by walking paths, small gardens, and old red buildings with typical Chinese curly roofs. The lake was once the royal garden in Qing Dynasty. Boya tower stands on a little hill beside the lake. The lake and the tower form a distinctive landscape and a symbol of Peking University.
Weiming Lake is a very good place for studying, reading, skating in the winter, and of course, jogging. More and more students and teachers run or walk around Weiming Lake every day and show how many paces they have covered in the mobile app WeChat Sports to get “Zans” (applauses).
ACMer X also enjoys jogging around Weiming Lake. His watch can measure and record an altitude value every meter. After a round of running, X collected the altitude data around the lake. Now he wants to find out the longest slope around the lake.
Input
There are no more than 20 test cases.
Each case has two lines.
The first line is an integer N (2 <= N <= 100) meaning that the length of the road around the lake is N meters. The second line contains N integers a1,a2...aN, (0<= a1,a2...aN <= 100) indicating N altitude sample values around the lake. The samples are given in clockwise order, and the distance between two adjacent samples is one meter. Of course the distance between a1 and aN is also one meter. The input ends by a line of 0. Output For each test case, print the length of the longest slope in meters. A slope is a part of the road around the lake, and it must keep going up or going down. If there are no slope, print 0. Sample Input 4 1 1 1 1 8 5 1 2 3 4 5 6 2 6 5 4 3 2 1 2 10 1 0 2 3 2 2 3 4 3 2 0 Sample Output 0 5 4 4 ============================================================== 最长连续上升子序列 将数组复制一遍连接起来，然后正着反着做两遍LICS就好了 ============================================================== [csharp] using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace What_a_Beautiful_Lake { class Program { static void Main(string[] args) { int n = 0; do { n = Convert.ToInt32(Console.ReadLine().Trim()); if (n == 0) break; int[] a = new int[n * 2]; string[] inp = Console.ReadLine().Trim().Split(' '); for (int i = 0; i < n; i++) { a[i] = Convert.ToInt32(inp[i]); a[i + n] = Convert.ToInt32(inp[i]); } int len = LICS(a); Array.Reverse(a); len = Math.Max(LICS(a), len); Console.WriteLine(len - 1); } while (true); } static int LICS(int[] A) { if (A.Length == 0) { return 0; } else if (A.Length == 1) { return 1; } int sublen = 0, templen = 1; for (int i = 1; i < A.Length; i++) { if (A[i] > A[i - 1]) { templen++; } else { templen = 1; } if (sublen < templen) { sublen = templen; } } return sublen; } } } [/csharp]

REPORT-hihoCoder太阁最新面经算法竞赛15(AC #1 #2 #3) – 16.11.19

REPORT-hihoCoder太阁最新面经算法竞赛15(AC #1 #2 #3) – 16.11.19

#1 Boarding Passes

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Boarding_Passes
{
class Program
{
static void Main(string[] args)
{

Dictionary<string, int> startcities = new Dictionary<string, int>();
Dictionary<string, int> endcities = new Dictionary<string, int>();
int startcitycount = 0, endcitycount = 0;
for (int i = 0; i < n; ++i)
{
if (!startcities.ContainsKey(inp[0]))
{
startcitycount++;
}
else
{
startcities[inp[0]]++;
}
if (!endcities.ContainsKey(inp[1]))
{
endcitycount++;
}
else
{
endcities[inp[1]]++;
}
}

foreach (var temp in startcities)
{
if (!endcities.ContainsKey(temp.Key) || endcities[temp.Key] + 1 == startcities[temp.Key])
{
Console.Write(temp.Key);
break;
}
}
Console.Write(" ");
foreach (var temp in endcities)
{
if (!startcities.ContainsKey(temp.Key) || startcities[temp.Key] + 1 == endcities[temp.Key])
{
Console.Write(temp.Key);
break;
}
}
}
}
}


#2 Sorting Photo Files

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Sorting_Photo_Files
{
class Program
{
static void Main(string[] args)
{
List<string> partStr = new List<string>();
Dictionary<string, List<int>> partInt = new Dictionary<string, List<int>>();
for (int i = 0; i < N; i++)
{
var sp = split(filename);
if (!partInt.ContainsKey(sp.Key))
{
List<int> l = new List<int>();
}
else
{
}
}
foreach(var temp in partInt)
{
temp.Value.Sort();
}
partStr.Sort();
foreach(var temp in partStr)
{
foreach (var temp2 in partInt[temp])
{
Console.WriteLine("{0}{1}", temp, temp2);
}
}
}
public static KeyValuePair<string, int> split(string str)
{
KeyValuePair<string, int> retdata = new KeyValuePair<string, int>();
for (int i = 0; i < str.Length; i++)
{
if (str[i] >= '0' && str[i] <= '9')
{
string partA = str.Substring(0, i);
string partB = str.Substring(i);
retdata = new KeyValuePair<string, int>(partA, Convert.ToInt32(partB));
break;
}
}
return retdata;
}
}
}



#3 Circle Detect

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Circle_Detect
{
class Program
{
static void Main(string[] args)
{
for (int Times = 0; Times < T; Times++) { string[] inp = Console.ReadLine().Trim().Split(' '); int n = Convert.ToInt32(inp[0]); int m = Convert.ToInt32(inp[1]); List[] g = new List[n + 5];
for (int i = 0; i < n + 5; i++) { g[i] = new List();
}
bool[] visited = new bool[n + 5];
for (int i = 0; i < n + 5; i++) visited[i] = false; for (int i = 0; i < m; i++) { inp = Console.ReadLine().Trim().Split(' '); int a = Convert.ToInt32(inp[0]) - 1; int b = Convert.ToInt32(inp[1]) - 1; if (!g[a].Contains(b)) g[a].Add(b); } bool flag = false; for (int i = 0; i < n; i++) { if (dfs(visited, i, g)) { flag = true; break; } } if (flag) Console.WriteLine("YES"); else Console.WriteLine("NO"); } } static bool dfs(bool[] vis,int p,List[] g)
{
if (vis[p]) return true;
vis[p] = true;
for (int i = 0; i < g[p].Count(); i++) { if (dfs(vis, g[p][i], g)) return true; } vis[p] = false; return false; } } }

HIHOCODER-WEEK123 重复次数最多的连续字串

HIHOCODER-WEEK123 重复次数最多的连续字串

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace HIHOCODER_WEEK123
{
class Program
{
static RMQ r;
const int MAXN = 100005;
static int[] wa = new int[MAXN];
static int[] wb = new int[MAXN];
static int[] ws = new int[MAXN];
static int[] wv = new int[MAXN];
static int[] rank = new int[MAXN];
static int[] height = new int[MAXN];
static int[] sa = new int[MAXN];
static int n;
static string ss;
static int[] aa = new int[MAXN];
static int[,] mn = new int[MAXN, 20];
static bool cmp(int[] r, int a, int b, int l)
{
return (r[a] == r[b]) && (r[a + l] == r[b + l]);
}
static void DA(int[] r, int[] sa, int n, int m)
{
int i, j, p;
int[] x = wa, y = wb, t = new int[MAXN];
for (i = 0; i < m; i++) ws[i] = 0;
for (i = 0; i < n; i++) ws[x[i] = r[i]]++;
for (i = 1; i < m; i++) ws[i] += ws[i - 1];
for (i = n - 1; i >= 0; i--) sa[--ws[x[i]]] = i;
for (j = 1, p = 1; p < n; j *= 2, m = p)
{
for (p = 0, i = n - j; i < n; i++) y[p++] = i;
for (i = 0; i < n; i++) if (sa[i] >= j) y[p++] = sa[i] - j;
for (i = 0; i < n; i++) wv[i] = x[y[i]];
for (i = 0; i < m; i++) ws[i] = 0;
for (i = 0; i < n; i++) ws[wv[i]]++;
for (i = 1; i < m; i++) ws[i] += ws[i - 1];
for (i = n - 1; i >= 0; i--) sa[--ws[wv[i]]] = y[i]; //基数排序部分
for (t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; i++)
x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++;  //更新名次数组x[],注意判定相同的
}
}
static void calheight(int[] r, int[] sa, int n)
{
int i, k = 0;
for (i = 0; i <= n; i++) rank[sa[i]] = i;
for (i = 0; i < n; i++)
{
if (k != 0) k--;
int j = sa[rank[i] - 1];
while (r[i + k] == r[j + k]) k++;
height[rank[i]] = k;
}
}
static int solve(int n)
{
int ans = 0;
for (int l = 1; l <= n; l++)
{
for (int i = 1; i + l <= n; i += l)
{
int ra = r.findRMQ(i, i + l,rank);
if (i - l + ra % l > 0)
ans = Math.Max(ans, r.findRMQ(i - l + ra % l, i + ra % l, rank) / l + 1);
}
}
return ans;
}

static void Main(string[] args)
{

n = ss.Length;
for (int i = 0; i < n; i++)
{
aa[i] = ss[i] - 'a' + 1;
}
aa[n] = 0;
DA(aa, sa, n + 1, 30);
calheight(aa, sa, n);
r = new RMQ(n, height, MAXN);
int ans = solve(n);
Console.WriteLine(ans);
}
}
class RMQ
{
int[,] dp;
public RMQ(int n, int[] array, int MAXM)
{
dp = new int[MAXM, Convert.ToInt32(Math.Log(MAXM) / Math.Log(2)) + 2];
for (int i = 1; i <= n; ++i)
{
dp[i, 0] = array[i];
}
for (int i = 1; (1 << i) <= n; i++)
{
for (int j = 1; j + (1 << i) - 1 <= n; j++)
{
dp[j, i] = Math.Min(dp[j, i - 1], dp[j + (1 << i - 1), i - 1]);
}
}
}
public int findRMQ(int  a, int b,int[] rank)
{

a--; b--;
int l = Math.Min(rank[a], rank[b]) + 1, r = Math.Max(rank[a], rank[b]);
int len = r - l + 1, i;
for (i = 0; (1 << i) <= len; i++) ;
i--;
int k = Convert.ToInt32(Math.Floor((Math.Log(r - l + 1)) / Math.Log(2)));
return Math.Min(dp[l, k], dp[r - (1 << k) + 1, k]);
}
}
}


RMQ问题-ST算法

RMQ问题-ST算法

ST算法（Sparse Table）
$$f(i,j) = min(f(i,j-1),f(i+{2}^{(j-1)},j-1))$$
$$f(i,j)$$是区间$$[i,i+{2}^{(j-1)}]$$中的最小值，$$f[i,0]=a[i]$$

    class RMQ
{
int[,] dp;
public RMQ(int n, int[] array, int MAXM)
{
dp = new int[MAXM, Convert.ToInt32(Math.Log(MAXM) / Math.Log(2)) + 2];
for (int i = 0; i < n; ++i)
{
dp[i, 0] = array[i];
}
for (int j = 1; (1 << j) <= n; j++)
{
for (int i = 0; i + (1 << j) - 1 < n; i++)
{
dp[i, j] = Math.Min(dp[i, j - 1], dp[i + (1 << (j - 1)), j - 1]);
}
}
}
public int findRMQ(int l, int r)
{
int k = Convert.ToInt32(Math.Floor((Math.Log(r - l + 1)) / Math.Log(2)));
return Math.Min(dp[l, k], dp[r - (1 << k) + 1, k]);
}
}

REPORT-hihoCoder太阁最新面经算法竞赛14(AC #1 #2 #3) – 16.11.12

REPORT-hihoCoder太阁最新面经算法竞赛14(AC #1 #2 #3) – 16.11.12

#1 Bigint Multiplication

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Bigint_Multiplication
{
class Program
{
static void calcmut(int[] n1, int[] n2, int[] res)
{
int pos = 0;
foreach (var n in n2)
{
int[] temp = new int[n1.Length + 1];
int co = 0;//carry-over
int ro = 0;//rest
for (int i = 0; i < n1.Length; ++i)
{
int t = n1[i] * n + co;
co = t / 10;
ro = t % 10;
temp[i] = ro;
}
if (co > 0) temp[n1.Length] = co;
co = 0;
for (int i = pos; i < temp.Length + pos; ++i)
{
int t = temp[i - pos] + co + res[i];
res[i] = t % 10;
co = t / 10;
}
pos++;
}
}
static void Main(string[] args)
{
string n1 = inp[0];
string n2 = inp[1];
int[] a1 = new int[n1.Length];
int[] a2 = new int[n2.Length];
int[] res = new int[(n1.Length + 1) * (n2.Length + 1)];
for (int i = n1.Length - 1; i >= 0; --i)
{
a1[n1.Length - i - 1] = Convert.ToInt32(n1[i]) - 48;
}
for (int i = n2.Length - 1; i >= 0; --i)
{
a2[n2.Length - i - 1] = Convert.ToInt32(n2[i]) - 48;
}
calcmut(a1, a2, res);
bool flag = false;
for (int i = 0; i < res.Length; ++i)
{
if ((res[res.Length - i - 1] == 0) && !flag) continue;
else { flag = true; }
Console.Write(res[res.Length - i - 1]);
}
if (!flag) Console.WriteLine(0);
}
}
}


#2数论一·Miller-Rabin质数测试

using System;

namespace Milonger_Rabin
{
class Program
{
static long multMod(long a, long b, long n)//a*b%n
{
long temp = 0;
while (b != 0)
{
if ((b & 1) == 1) temp = (temp + a) % n;
a = (a + a) % n;
b >>= 1;
}
return temp;
}
static long powerMod(long a, long b, long n)//a^b%n
{
long temp = 1;
while (b != 0)
{
if ((b & 1) == 1) temp = multMod(temp, a, n);
a = multMod(a, a, n);
b >>= 1;
}
return temp;
}
static long[] arrayA = new long[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 };

static bool Witness(long a, long n)
{
long m = n - 1;
int j = 0;
while ((m & 1)==0)
{
j++;
m >>= 1;
}
long x = powerMod(a, m, n);
if (x == 1 || x == n - 1) return false; // n may be prime
while (j-->0)
{
//    x = exp_mod(x,2,n);
x = x * x % n;
if (x == n - 1) return false;
}
return true; //n must be composite
}

static bool miller_rabin(long n, int S)
{
if (n == 2 || n == 3 || n == 5 || n == 7 || n == 11) return true;
if (n == 1 || (n % 2) == 0 || (n % 3) == 0 || (n % 5) == 0 || (n % 7) == 0 || (n % 11) == 0) return false;

long x, pre, u;
int i, j, k = 0;
u = n - 1;

while ((u & 1)==0)
{
k++; u >>= 1;
}

Random r = new Random();
for (i = 0; i < S; ++i)
{
x = r.Next() % (n - 2) + 2;
if ((x % n) == 0) continue;

x = powerMod(x, u, n);
pre = x;
for (j = 0; j < k; ++j)
{
x = multMod(x, x, n);
if (x == 1 && pre != 1 && pre != n - 1) return false;
pre = x;
}
if (x != 1) return false;
}
return true;
}

static void Main(string[] args)
{
for (long i = 0; i < n; i++)
{
Console.WriteLine(miller_rabin(k, 12)?"Yes":"No");
}
}
}
}


#3数论二·Eular质数筛法

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace EularPrimeSieve
{
class Program
{
static int Sieve(int n)
{
bool[] prime = new bool[1000005];
for (int i = 0; i < prime.Length; i++) prime[i] = true;
int[] primeList = new int[100000];
int primeCount = 0;
for (int i = 2; i <= n; ++i)
{
if (prime[i])
{
primeList[++primeCount] = i;
}
for (int j = 1; j <= primeCount; ++j)
{
if (primeList[j] * i > n)
{
break;
}
prime[i * primeList[j]] = false;
if (i % primeList[j] == 0)
{
break;
}
}
}
return primeCount;
}
static void Main(string[] args)
{
Console.WriteLine(Sieve(n));
}
}
}

HIHOCODER-WEEK122 最长公共子串

HIHOCODER-WEEK122 最长公共子串

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace HIHOCODER_WEEK122
{
class Program
{
static void Main(string[] args)
{
LCS lcs = new LCS(str1, str2);
Console.WriteLine(lcs.Length);
}
}
class LCS
{
public int Length { get; private set; }
public LCS(string str1,string str2)
{
Length = 0;
int lStr1 = str1.Length;
int lStr2 = str2.Length;
if (lStr1 == 0 || lStr2 == 0)
{
Length = 0;
return;
}
int[,] table = new int[lStr1, lStr2];
int longest = 0;
for (int i = 0; i < lStr2; ++i)
table[0, i] = (str1[0] == str2[i] ? 1 : 0);
for (int i = 1; i < lStr1; ++i)
{
table[i, 0] = (str1[i] == str2[0] ? 1 : 0);

for (int j = 1; j < lStr2; ++j)
{
if (str1[i] == str2[j])
{
table[i, j] = table[i - 1, j - 1] + 1;
}
}
}
for (int i = 0; i < lStr1; ++i)
{
for (int j = 0; j < lStr2; ++j)
{
if (longest < table[i, j])
{
longest = table[i, j];
}
}
}
Length = longest;
}
}
}



//code source：http://www.xuebuyuan.com/2116000.html
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn = 420000;
int s[maxn], rs[maxn], sa[maxn], t[maxn], t2[maxn], c[maxn], Rank[maxn], height[maxn];
int n, m, k, tt, l1, l2;
char s1[maxn], s2[maxn];
#define min(x,y) x>y?y:x
#define max(x,y) x<y?y:x
inline int idx(char s)
{
return s - 'a' + 2;
}
void getheight(int n)
{
int i, k = 0;
for (i = 0; i <= n; i++) Rank[sa[i]] = i;
for (i = 0; i < n; i++)
{
if (k) k--;
int j = sa[Rank[i] - 1];
while (s[i + k] == s[j + k]) k++;
height[Rank[i]] = k;
}
}
void build_ss(int m, int n)
{
n++;
int i, *x = t, *y = t2;
for (int i = 0; i < m; i++) c[i] = 0;
for (int i = 0; i < n; i++) c[x[i] = s[i]]++;
for (int i = 1; i < m; i++) c[i] += c[i - 1];
for (int i = n - 1; i >= 0; i--)
sa[--c[x[i]]] = i;
for (int k = 1; k <= n; k <<= 1)
{
int p = 0;
for (i = n - k; i < n; i++) y[p++] = i;
for (i = 0; i < n; i++) if (sa[i] >= k) y[p++] = sa[i] - k;

for (i = 0; i < m; i++) c[i] = 0;
for (i = 0; i < n; i++) c[x[y[i]]]++;
for (i = 1; i < m; i++) c[i] += c[i - 1];
for (i = n - 1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i];
swap(x, y);
p = 1;
x[sa[0]] = 0;
for (i = 1; i < n; i++)
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;
}
}
bool diff(int x, int y)
{
int a = min(x, y);
int b = max(x, y);
if (a<l1 && b>l1) return true;
return false;
}
int main()
{
cin >> s1;
cin >> s2;
l1 = strlen(s1);
l2 = strlen(s2);
for (int i = 0; i < l1; i++)
s[i] = idx(s1[i]);
s[l1] = 0;
n = l1 + 1;
for (int i = 0; i < l2; i++)
{
s[n++] = idx(s2[i]);
}
s[n] = 1;
build_ss(128, n);
getheight(n);
int ans = 0;
for (int i = 2; i < n; i++)
{
if (diff(sa[i], sa[i - 1]))
ans = max(ans, height[i]);
}
cout << ans;
return 0;
}