Cod sursa(job #1763095)

Utilizator Kira96Denis Mita Kira96 Data 24 septembrie 2016 12:01:42
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <cstdio>
#include <fstream>
#include <vector>

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

#define N 2000100

vector<int> sol;
string a, b, s;
int z[N], n, k;

int main() {
    
    f >> a >> b;
    string s = "0";
    for (int i = 0; i < a.length(); ++i) {
        s += a[i];   
    }
    s += '#';
    for (int i = 0; i < b.length(); ++i) {
        s += b[i];
    }
    n = s.length() - 1;
    k = 1; // numarul pt care k + z[k] - 1 e maxim
    for (int i = 2; i <= n; ++i) {
    	if (k + z[k] - 1 < i) {
    		int p = i;
    		for (int j = 1; p <= n && s[p] == s[j]; ++p, ++j);
    		z[i] = p - i;
    		k = i;
    	} else {
    		z[i] = z[i - k + 1];
    		if (z[i] + i - 1 > k + z[k] - 1) {
    			z[i] = z[k] + k - 1 - (i - 1);
    		}
    		for (;z[i] + i <= n && s[z[i] + i] == s[z[i] + 1]; ++z[i]);
    	}
    }
    for (int i = a.length() + 1; i <= n; ++i) {
        if (z[i] >= a.length()) {
            sol.push_back(i - a.length() - 2);
        }
    }
    g << sol.size() << "\n";
    for (int i = 0; i < min((int)sol.size(), 1000); ++i) {
        g << sol[i] << " ";
    }
    return 0;
}