22) Поиск общих касательных к двум окружностям
Даны две окружности. Требуется найти все их общие касательные, т.е. все такие прямые, которые касаются обеих окружностей одновременно.
Описанный алгоритм будет работать также в случае, когда одна (или обе) окружности вырождаются в точки. Таким образом, этот алгоритм можно использовать также для нахождения касательных к окружности, проходящих через заданную точку.
struct pt {
double x, y;
pt operator- (pt p) {
pt res = { x-p.x, y-p.y };
return res;
}
};
struct circle : pt {
double r;
};
struct line {
double a, b, c;
};
const double EPS = 1E-9;
double sqr (double a) {
return a * a;
}
void tangents (pt c, double r1, double r2, vector<line> & ans) {
double r = r2 - r1;
double z = sqr(c.x) + sqr(c.y);
double d = z - sqr(r);
if (d < -EPS) return;
d = sqrt (abs (d));
line l;
l.a = (c.x * r + c.y * d) / z;
l.b = (c.y * r - c.x * d) / z;
l.c = r1;
ans.push_back (l);
}
vector<line> tangents (circle a, circle b) {
vector<line> ans;
for (int i=-1; i<=1; i+=2)
for (int j=-1; j<=1; j+=2)
tangents (b-a, a.r*i, b.r*j, ans);
for (size_t i=0; i<ans.size(); ++i)
ans[i].c -= ans[i].a * a.x + ans[i].b * a.y;
return ans;
}
23) Z-функция строки и её вычисление
Пусть
дана строка 
длины
.
Тогда Z-функция ("зет-функция")
от этой строки — это массив длины
,
-ый
элемент которого равен наибольшему
числу символов, начиная с позиции
,
совпадающих с первыми символами строки
.
Иными
словами, 
—
это наибольший общий префикс строки
и
её
-го
суффикса.
vector<int> z_function (string s) {
int n = (int) s.length();
vector<int> z (n);
for (int i=1, l=0, r=0; i<n; ++i) {
if (i <= r)
z[i] = min (r-i+1, z[i-l]);
while (i+z[i] < n && s[z[i]] == s[i+z[i]])
++z[i];
if (i+z[i]-1 > r)
l = i, r = i+z[i]-1;
}
return z;
}
24) Префикс-функция. Алгоритм Кнута-Морриса-Пратта
vector<int> prefix_function (string s) {
int n = (int) s.length();
vector<int> pi (n);
for (int i=1; i<n; ++i) {
int j = pi[i-1];
while (j > 0 && s[i] != s[j])
j = pi[j-1];
if (s[i] == s[j]) ++j;
pi[i] = j;
}
return pi;
}
КМП
/* Preprocessing */
void PRE_KMP( char *x, int m, int kmp_next[] ) {
int i, j;
i=0;
j=kmp_next[0]=-1;
while ( i < m ) {
while ( j > -1 && x[ i ] != x[ j ] ) j=kmp_next[ j ];
i++;
j++;
if ( x[ i ] == x[ j ] ) kmp_next[i]=kmp_next[j];
else kmp_next[ i ] = j;
}
}
void KMP( char *x, char *y, int n, int m ) {
int i, j, kmp_next[XSIZE];
/* Preprocessing */
PRE_KMP(x, m, kmp_next );
/* Searching */
i=j=0;
while ( i < n ) {
while ( j > -1 && x[ j ] != y[ i ] ) j = kmp_next[ j ];
i++;
j++;
if ( j >= m ) {
OUTPUT( i - j );
j = kmp_next[ j ];
}
}
}
25) Нахождение всех подпалиндромов
bool is_poly(const string& S, int i, int j)
{
if (i == j)
return false;
while (i < j)
{
++i;
--j;
if (S[i] != S[j])
return false;
}
return true;
}
//*
int poly ( const string &S ) {
int count = 0;
int size = S.size();
if (1 == size)
return 1;
int j = 0;
for( int i = 0; i < size-1;++i)
{
char begin = S[i];
j = S.find_last_of(begin, size-begin-1);
while( -1 != j)
{
bool is_p = is_poly(S, i, j);
if (is_p)
{
++count;
}
j = S.find_last_of(begin,j-1);
if ( i >= j )
break;
}
}
return count;
}