Конкатенація

Конкатенація (лат. concatēnāre, об'єднання, з'єднання) — в загальному сенсі - функція з'єднання двох сутностей або результат такої операції.

Конкатенація в програмуванні - послідовне з'єднання значень декількох змінних та повернення результуючого значення. Аргументами такої функції можуть бути такі сутності, як рядки або масиви, результатом - ланцюжок цих сутностей.

Приклади:

• конкатенація слів «мікро» і «світ» дасть слово «мікросвіт».
• конкатенація рядків «34» та «84» дають результат «3484».

У математиці

Конкатенація — бінарна операція, визначена на словах даного алфавіту. Якщо $\alpha =a_1\dots a_n$ і $\beta =b_1\dots b_m$ слова в алфавіті $A$, то конкатенацією слів $\alpha$і $\beta$, яку позначимо в цій статті як $\alpha \cdot \beta$, буде слово $\gamma$в тому ж алфавіті $A$, що визначається рівністю

$\gamma =\alpha \cdot \beta =a_1\dots a_n{b}_1\dots b_m$.

Наприклад, якщо $\alpha =media$ і $\beta =wiki$ слова в алфавіті $A=\{a,b,c,\dots ,z\}$, що містить всі літери латинського алфавіту, то

$\gamma =\alpha \cdot \beta =media\cdot wiki=mediawiki$.

Властивості конкатенації

• Операція конкатенації асоціативна.
• Операція конкатенації некомутативна. Дійсно, $wiki\cdot media=wikimedia$, але $media\cdot wiki=mediawiki\ne wikimedia$. Від перестановки операндів змінюється результат операції, що й означає її некомутативність.
• Порожнє слово, $\epsilon$, є нейтральним елементом (одиницею) операції конкатенації. Тобто, якщо $\epsilon$- порожнє слово, то для будь-якого слова $\alpha$ виконана рівність:

$\epsilon \cdot \alpha =\alpha \cdot \epsilon =\alpha$.

• Множина $A^{*}$ всіх слів у алфавіті утворює моноїд (так звана «вільна напівгрупа»).
• Множина $A^{*}\setminus \{\epsilon \}$ всіх непустих слів у алфавіті утворює напівгрупу.
• Довжина конкатенації слів дорівнює сумі довжин операндів:

$|\alpha \cdot \beta |=|\alpha |+|\beta |$.

Піднесення до степеня

Операція конкатенації слів, подібно операції множення чисел, породжує операцію піднесення до степеня. Нехай $\alpha$ деяке слово в алфавіті $A$ , а $n$ ціле невід'ємне число. Тоді $n$-м ступенем слова $\alpha$, що позначається ${\alpha }^n$, буде слово $\gamma$ в тому ж алфавіті $A$, визначене рівністю:

$\begin{array}{cc}\gamma ={\alpha }^n=& \underbrace{\alpha \cdot \dots \cdot \alpha }\\ & n\end{array}$

У випадку $n=0$, степінь ${\alpha }^0$за визначенням буде рівною порожньому слову, $\epsilon$.

В інформатиці

Операція конкатенації визначається для типів даних, які мають структуру послідовності (список, чергу, масив і ряд інших). У загальному випадку, результатом конкатенації двох об'єктів $A$ і $B$ є об'єкт $C=A\cdot B$, отриманий почерговим додаванням всіх елементів об'єкта $B$, починаючи з початку, в кінець об'єкта $A$.

З міркувань зручності й ефективності розрізняють дві форми операції конкатенації:

1. Модифікуюча конкатенація. Результат операції формується в лівому операнді.
2. Немодифікуюча конкатенація. Результатом є новий об'єкт, операнди залишаються незмінними.

Алгоритм

Алгоритм конкатенації на прикладі двох масивів наведений нижче.

Дано:

1. Масив $A$ з розміром $N$.
2. Масив $B$ з розміром $M$.
3. Масив $C$ з розміром $M+N$, що є результатом конкатенації масивів $A$ та $B$.
4. Індекс масиву $I$.

Суть алгоритму:

1. Виконати копіювання масиву $A$ в масив $C$ для $I\in 1,2,...M$:

$C[I]\leftarrow A[I]$

2. Виконати копіювання масиву $B$ в масив $C$ для $I\in 1,2,...N$:

$C[M+I]\leftarrow B[I]$

3. END

В мовах програмування

C

В мові програмування C функція конкатенації рядків strcat міститься в бібліотеці <string.h> .

#include <stdio.h> 
#include <string.h> 

#define N 50

void main() 
{ 
	// Декларація змінної example
	char example[N]; 
    // Копіювати рядок в змінну example
	strcpy(example, "Кон"); 
	// Виконати конкатенацію значення змінної example
	strcat(example, "катенація");
	// Вивести на екран змінну example
	printf("%s\n", example); 
}