Cod sursa(job #1923408)

Utilizator Joystick6208Catalin Topala Joystick6208 Data 10 martie 2017 23:54:18
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

char p[2000005], t[2000005];
int pi[2000005], rez[1005], ans;

void citeste()
{
	
	cin.get(p+1, 2000005);
	cin.get();
	cin.get(t+1, 2000005);
	
}

void kmp()
{

    int n = strlen(t);
    int m = strlen(p);

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

        pi[i] = k;
    }

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

        if(k == m)
        {
            ++ans;
			if(ans <= 1000)
				rez[ans] = i-m;

			k = pi[k];
        }
    }

}

void afis()
{
    cout << ans << '\n';
    for(int i = 1; i <= min(ans, 1000); ++i)
        cout << 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;
}