Cod sursa(job #1763112)

Utilizator Kira96Denis Mita Kira96 Data 24 septembrie 2016 12:08:30
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <cstdio>
#include <fstream>
#include <vector>

using namespace std;

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

#define N 4000100

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

int main() {
    
    f >> a >> b;
    string s = "0";
    s += a;
    s += '#';
    s += b;
    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] = min(z[i - k + 1], k + z[k] - 1 - (i - 1));
    		for (;z[i] + i <= n && s[z[i] + i] == s[z[i] + 1]; ++z[i]);
            if (i + z[i] - 1 > k + z[k] - 1) {
                k = 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;
}