#include <iostream>

using namespace std;

void generujTablicePrefiksoSufiksow(string wzorzec, int tablicaPrefiksoSufiksow[]) {
    int j = 0;
    int i = 1;
    
    tablicaPrefiksoSufiksow[0] = 0;
    while (i < wzorzec.size()) {
        if (wzorzec[i] == wzorzec[j]) {
            j++;
            tablicaPrefiksoSufiksow[i] = j;
            i++;
        } else {
            if (j != 0) {
                j = tablicaPrefiksoSufiksow[j - 1];
            } else {
                tablicaPrefiksoSufiksow[i] = j;
                i++;
            }
        }
    }
}

int wyszukajKMP(string wzorzec, string napis) {
    int tablicaPrefiksoSufiksow[wzorzec.size()] = {};
    generujTablicePrefiksoSufiksow(wzorzec, tablicaPrefiksoSufiksow);
    
    int i = 0, j = 0;
    
    while (i < napis.size()) {
        if (wzorzec[j] == napis[i]) {
            j++; i++;
        }
        if (j == wzorzec.size()) {
            return (i - j);
            j = tablicaPrefiksoSufiksow[j - 1];
        }
        else if (i < napis.size() && wzorzec[j] != napis[i]) {
            if (j != 0) {
                j = tablicaPrefiksoSufiksow[j - 1];
            } else {
                i++;
            }
        }
    }
    return -1;
}

int main() {

    string DNA[6] = {
        "aaacaaagctgctta",
        "aacaaagtgatgtgg",
        "aacccactgccttta",
        "aagaacggtcaatgt",
        "aagagtaaattgtga",
        "aaggcaagtgagccg"
        
    };

    string gen = "atgt";

    int rezultat = 0;
    for (int i = 0; i < sizeof(DNA)/sizeof(DNA[0]); i++) {
        rezultat = wyszukajKMP(gen, DNA[i]);
        if (rezultat >= 0) {
            cout << "TAK" << endl;
        } else {
            cout << "NIE" << endl;
        }
    }

    return 0;
}

public class Main {
    static int[] budowaTablicyKMP(String wzorzec) {
        int rozmiarT = wzorzec.length() + 1;
        int[] T = new int[rozmiarT];
        int poz = -1;
        T[0] = -1;

        for (int i = 1; i < rozmiarT; ++i) {
            while(poz > -1 && wzorzec.charAt(poz) != wzorzec.charAt(i - 1)) {
                poz = T[poz];
            }
            ++poz;

            if (i == rozmiarT - 1 || wzorzec.charAt(i) != wzorzec.charAt(poz)) {
                T[i] = poz;
            }
            else {
                T[i] = T[poz];
            }
        }

        return T;
    }

    static String szukajWzorcaKMP(String wzorzec, String tekst) {
        int[] tablicaDopasowan = budowaTablicyKMP(wzorzec);

        int b = 0;
        for (int i = 0; i < tekst.length(); ++i) {
            while (b > -1 && wzorzec.charAt(b) != tekst.charAt(i)) {
                b = tablicaDopasowan[b];
            }
            ++b;

            if (b == wzorzec.length()) {
                return "TAK";
            }
        }
        return "NIE";
    }

    public static void main(String[] args) {
        String gen = "atgt";
        String[] DNA = {"aaacaaagctgctta", "aacaaagtgatgtgg", "aacccactgccttta", "aagaacggtcaatgt", "aagagtaaattgtga", "aaggcaagtgagccg"};
        
        for (int j = 0; j < DNA.length; ++j) {

        System.out.println(szukajWzorcaKMP(gen, DNA[j]));
        }    

    }
}

gen = "atgt"
DNA = ["aaacaaagctgctta", "aacaaagtgatgtgg", "aacccactgccttta", "aagaacggtcaatgt", "aagagtaaattgtga", "aaggcaagtgagccg"]

def budowa_tablicy_KMP(wzorzec):
	rozmiar_tablicy = len(wzorzec) + 1
	tablica = [0] * rozmiar_tablicy
	poz = tablica[0] = -1

	for i in range(1, rozmiar_tablicy):
		while poz > -1 and wzorzec[poz] != wzorzec[i - 1]:
			poz = tablica[poz]
		poz += 1

		if i == rozmiar_tablicy - 1 or wzorzec[i] != wzorzec[poz]:
			tablica[i] = poz
		else:
			tablica[i] = tablica[poz]

	return tablica


def szukaj_algorytmem_KMP(wzorzec, tekst):
	
	tablica_T = budowa_tablicy_KMP(wzorzec)
	dop = 0
	czy_wystepuje = "NIE"
	for indeks, znak_S in enumerate(tekst):			
		while dop > - 1 and wzorzec[dop] != znak_S:
			dop = tablica_T[dop]
		dop += 1
		if dop == len(wzorzec):
			czy_wystepuje = "TAK"
			break
	return czy_wystepuje

for i in range(0,len(DNA)):
    print(szukaj_algorytmem_KMP(gen, DNA[i]))

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string sortuj(string wyraz) {
	sort(wyraz.begin(), wyraz.end());

	return wyraz;
}

bool kolejne(string T) {
	return T[0] + 1 == T[1] && T[1] + 1 == T[2] && T[2] + 1 == T[3];
}

int main() {
	int licznik = 0;
	string hasla[] = {"A5mnpoR89cd", "A5876RRcg", "As45FGHFEk90nba", "ahwwcpo"};
	int ile_hasel = sizeof(hasla)/sizeof(hasla[0]);
    
	for (int i = 0; i < ile_hasel; i++) {
		for (int j = 0; j < hasla[i].size() - 3; j++) {
			string pom = hasla[i].substr(j, 4);
			if (kolejne(sortuj(pom)))
            {
                licznik++;
                break;
            }
		}
	}

	cout<<licznik;
}

import java.util.*;
import java.lang.*;

public class Main {
	public static String sortuj(String wyraz) {
		char tymczasowa[] = wyraz.toCharArray(); 
		Arrays.sort(tymczasowa);

		return new String(tymczasowa);
	}
 
	public static boolean kolejne(String wyraz) {
		return wyraz.charAt(0) + 1 == wyraz.charAt(1) && wyraz.charAt(1) + 1 == wyraz.charAt(2) && wyraz.charAt(2) + 1 == wyraz.charAt(3);
	}
 
	public static void main(String[] args) throws java.lang.Exception {
		int licznik = 0;
		String hasla[] = {"A5mnpoR89cd", "A5876RRcg", "As45FGHFEk90nba", "ahwwcpo"};

		for (int i = 0; i < hasla.length; i++) {
			for (int j = 0; j < hasla[i].length() - 3; j++) {
				String pom = "";

				for (int k = 0; k < hasla.length; k++) {
					pom += hasla[i].charAt(j + k);
				}
 
				if (kolejne(sortuj(pom)))
                {
                    licznik++;
            		break;
                }
			}
		}

		System.out.println(licznik);
	}
}

def sortuj(wyraz):
	return ''.join(sorted(wyraz))

def kolejne(T):
	return chr(ord(T[0]) + 1) == T[1] and chr(ord(T[1]) + 1) == T[2] and chr(ord(T[2]) + 1) == T[3]

licznik = 0
hasla = ["A5mnpoR89cd", "A5876RRcg", "As45FGHFEk90nba", "ahwwcpo"]

for i in range(0, len(hasla)):
	for j in range(0, len(hasla[i]) - 3):
		if kolejne(sortuj(hasla[i][j:j + 4])):
			licznik += 1
			break

print(licznik)

#include <iostream>
#include <string>
using namespace std;

int main() {
	int licznik = 0;
	string hasla[] = {"A5mnpoR89cd", "A5876RRcg", "As45FGHFEk90nba", "ahwwcpo"};
    int ile_hasel = sizeof(hasla)/sizeof(hasla[0]);

	for (int i = 0; i < ile_hasel; i++) {
		bool wielka = false;
		bool mala = false;
		bool numer = false;

		for (int j = 0; j < hasla[i].size(); j++) {
			if (hasla[i][j] >= 'A' && hasla[i][j] <= 'Z') wielka = true;
			if (hasla[i][j] >= 'a' && hasla[i][j] <= 'z') mala = true;
			if (hasla[i][j] >= '0' && hasla[i][j] <= '9') numer = true;
		}

		if (wielka && mala && numer)
			licznik++;
	}

	cout<<licznik;
}

public class Main {
	public static void main(String[] args) throws java.lang.Exception {
		int licznik = 0;
		String hasla[] = {"A5mnpoR89cd", "A5876RRcg", "As45FGHFEk90nba", "ahwwcpo"};

		for (int i = 0; i < hasla.length; i++) {
			boolean wielka = false, mala = false, numer = false;

			for (int j = 0; j < hasla[i].length(); j++) {
				if (hasla[i].charAt(j) >= '0' && hasla[i].charAt(j) <= '9') {
					numer = true;
				}

				if (hasla[i].charAt(j) >= 'a' && hasla[i].charAt(j) <= 'z') {
					mala = true;
				}

				if (hasla[i].charAt(j) >= 'A' && hasla[i].charAt(j) <= 'Z') {
					wielka = true;
				}
			}

			if (numer && mala && wielka) {
				licznik ++;
			}
 
		}

		System.out.println(licznik);
	}
}

licznik = 0
hasla = ["A5mnpoR89cd", "A5876RRcg", "As45FGHFEk90nba", "ahwwcpo"]

for i in range(0, len(hasla)):
	wielka = False
	mala = False
	numer = False

	for j in range(0, len(hasla[i])):
		if hasla[i][j] >= 'A' and hasla[i][j] <= 'Z':
			wielka = True
		if hasla[i][j] >= 'a' and hasla[i][j] <= 'z':
			mala = True
		if hasla[i][j] >= '0' and hasla[i][j] <= '9':
			numer = True
	if wielka and mala and numer:
		licznik += 1

print(licznik)