Cod sursa(job #3212224)

Utilizator AlexMoto2006Motoasca Alexandru-Lucian AlexMoto2006 Data 11 martie 2024 13:12:12
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
// ConsoleApplication2.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <fstream>
#include <vector>
#include <string>

using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

string A, B;
int pos;
vector <int> app;
int kmp[1001];

int main() {
    cin >> A >> B;
    for (int i = 1; i < A.size(); i++)
    {
        int j= kmp[i - 1];
        while (j > 0 && A[i] != A[j])
			j = kmp[j - 1];
        if (A[i] == A[j])
        {
            j++;
            kmp[i] = j;
        }
    }
    for (int i = 0; i < B.size(); i++)
    {
        while (pos > 0 && B[i] != A[pos])
        {
            pos = kmp[pos - 1];	
        }
        if (B[i] == A[pos])
        {
			pos++;
            if (pos == A.size())
            {
				app.push_back(i - A.size() + 1);
				pos = kmp[pos - 1];
			}
		}
    }
    cout << app.size() << "\n";
    for(int i=0;i<min((int)app.size(),1000);i++)
		cout << app[i] << " ";
    return 0;
}