Cod sursa(job #1923393)

Utilizator Joystick6208Catalin Topala Joystick6208 Data 10 martie 2017 23:34:39
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

string t, p;
vector<int> rez;

void citeste()
{
	
	getline(cin, p);
	getline(cin, t);
	
}

void kmp()
{

    int n = t.size();
    int m = p.size();

    int pi[m];
    pi[0] = 0;

    int k = 0;
    for(int i = 1; i < m; ++i)
    {
        while(k > 0 && p[k+1] != p[i])
            k = pi[k-1];
        if(p[k+1] == p[i])
            k = k+1;

        pi[i] = k;
    }

    k = 0;
    for(int i = 0; i < n; ++i)
    {
        while(k > 0 && p[k+1] != t[i])
            k = pi[k-1];
        if(p[k+1] == t[i])
            k = k+1;

        if(k == m-1 && i-m+1 >= 0)
        {
            rez.push_back(i-m+1);
            k = pi[k-1];
        }
    }

}

void afis()
{
    int len = rez.size(), minim = min(len, 1000);

    printf("%d\n", len);
    for(int i = 0; i < min(len, 1000); ++i)
        printf("%d ", rez[i]);
}

int main()
{
	ios_base::sync_with_stdio(false);

	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);

	citeste();
	kmp();
	afis();

	return 0;
}