// Поиск подстроки в строке

// подпоследовательность = не обязательно подряд
// !!! подстрока = отрезок

string s;
string = vector<char>
for (int i = 0; i < n; i++)
	s += 'a';

// s = aaaaaaaaaaaaaaaaaaaaaaaaaaaaa
// p = aaaaaabaaaaaaa
// |s|=2n
// |p|=n
// n -> 2*n
// |s|+|p|
// |s|*|p|
uint32_t i = s.find(p) // std::npos (-1)
for (int i = 0, j; (j = s.find(p, i)) != std::npos; i = j + 1)
	;

char t[100 + 1]; // '\x0'
char p[50 + 1];

char *q = strstr(t, p) // 0
for (char *x = t; (x = strstr(x, p)) != 0; x++) 
	i = x - t

string s; // char* s.data() s.c_str()
char s[100]; 
readWord(s)


void prefixFunction(string s) {
	int n = s.size();
	vector<int> p(n + 1); // p[i]
	int k = 0;
	for (int i = 2; i <= n; i++) { // i - длина, s[i-1]
		// int k = p[i-1]; // 0
		while (k > 0 && s[i-1] != s[k])
			k = p[k]; // <= n
		if (s[i-1] == s[k])
			k++; // <= n
		p[i] = k;
	}
	// итого время работы O(n)
}
// Поиск подстроки в строке через p[] : КМП
// Кнута Мориса Пратта

void zFunction(string s) {
	int n = s.size()
	vector<int> z(n); // z[0]=0
	int L = -1, R = -1; // [L,R)
	for (int i = 1; i < n; i++) {
		k = (R <= i ? 0 : min(z[i-L],R-i));
		while (s[k] == s[i+k])
			k++;
		z[i] = k;
		if (i + k > R)
			L = i, R = i + k;
	}
}

const int P = 1000;
const int MOD = 1e9 + 7;

struct num {
	int x;
	num operator * (num a) {  
		return {(int64_t)x * a.x % MOD};
	};
	operator int () const {

	}
}

string s;
int n = s.size();
vector<num> deg(n + 1);
vector<num> h(n + 1);
deg[0] = 1;
h[0] = 0;
for (int i = 0; i < n; i++) {
	deg[i + 1] = deg[i] * P; // % MOD
	h[i + 1] = h[i] * P + s[i];
}

// [L,R)
auto getHash(int L, int R) {
	return h[R] - h[L] * deg[R - L];
}

// Типа данных
// MOD1 = 1e9 + 7 | int64_t
// MOD2 = 1e9 + 9;
// MOD1*MOD2 = (1e9 + 7)(1e9 + 9);
// __int128 // 64-бит
// MOD=1e18+3

// Рабин-Карп

string t, s;
num hs = 0, deg = 1;
for (char c : s) hs = hs*P + c;
forn(i, |s|)
	deg *= P;

num ht;
ht = ht*P + tc - x*deg;

// Общая подстрока

string s, t;
int l = 0, r = min(|s|,|t|)+1;
// l: да, r: нет
while (r - l > 1) { 
	if (check(m=(l+r/2)).first != -1)
		l = m;
	else
		r = m;
}
pair<int,int> check(int k) {
	unordered_map<int64_t,int> m(n);
	for (int i = 0; i + k <= s.size(); i++)
		m[hs.getHash(i, i+k)] = i;
	for (int i = 0; i + k <= t.size(); i++)
		if (m.count(h=ht.getHash(i, i+k)))
			return {m[h], i};
	return {-1, -1};
}
// nlogn (существуют Time=n, Space=min(|s|,|t|))

string s;
int n = s.size();
vector<uint64_t> deg(n + 1);
vector<uint64_t> h(n + 1);
deg[0] = 1;
h[0] = 0;
for (int i = 0; i < n; i++) {
	deg[i + 1] = deg[i] * P; // % 2^{64}
	h[i + 1] = h[i] * P + s[i]; // % 2^{64}
}

// [L,R)
auto getHash(int L, int R) {
	return h[R] - h[L] * deg[R - L]; // % 2^{64}
}