Cod sursa(job #1769980)

Utilizator danalex97Dan H Alexandru danalex97 Data 3 octombrie 2016 16:37:23
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
 
ifstream F("strmatch.in");
ofstream G("strmatch.out");
 
const int N = 2000010;
 
int z[N*2],n,m;
char a[N*2];
 
int cans;
vector<int> ans;
 
void expand(int& l, int& r) {
	while (a[r - l + 1   + 1] == a[r + 1] && r + 1 <= n) {
		++r;
	}
}
 
int main()
{
    F>>(a+1);
    m = strlen(a+1);
    F>>(a+m+1);
    n = strlen(a+1);
   
	int l = 0 , r = 0;
	for (int i = 2; i <= n ; ++i) {
		if (i > r) {
			if (a[i] == a[1]) {			
				l = r = i;
				expand(l, r);
				z[i] = r - l + 1;
			}
		} else {
			if (i + z[i - l + 1] - 1 < r) {
				z[i] = z[i - l + 1];
			} else {
				l = i;
				expand(l, r);
				z[i] = r - l + 1;
			}
		}
	}
   
	for (int i=m+1;i<=n;++i)
        if ( z[i] >= m )
        {
            cans++;
            if ( cans <= 1000 )
                ans.push_back(i-m);
        }
    G<<cans<<'\n';
    for (int i=0;i<int(ans.size());++i)
        G<<ans[i]-1<<' ';
    G<<'\n';
    
}