Cod sursa(job #2338009)

Utilizator LucaSeriSeritan Luca LucaSeri Data 6 februarie 2019 21:28:07
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <bits/stdc++.h>
 
using namespace std;

const int MAXN = 2e5 + 10;

string a, b;
int pi[MAXN];

int main() {
	#ifdef BLAT
		freopen("input", "r", stdin);
		#define f cin
		#define g cout
	#else
		ifstream f("strmatch.in");
    	ofstream g("strmatch.out");
    #endif

    f >> a >> b;
    int n = a.size();
    a = ' ' + a + "#" + b;
    
    int cnt = 0;
    vector< int > sol;

    int q = 0;
    for(int i = 2; i < a.size(); ++i) {
    	while(q && a[i] != a[q + 1]) q = pi[q];
    	if(a[i] == a[q + 1]) ++ q;
    	pi[i] = q;

    	if(q == n) {
    		++cnt;
    		q = pi[q];
    		if(cnt <= 1000) sol.emplace_back(i - 2*n - 1);
    	}
    }


    g << cnt << '\n';

    for(auto &x : sol) g << x << ' ';
    return 0;
}