Cod sursa(job #1358083)

Utilizator danalex97Dan H Alexandru danalex97 Data 24 februarie 2015 12:41:13
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 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;

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] ) continue;

            l = r = i;
            while ( a[r+1] == a[r-l+2] && r+1 <= n )
                ++r;
            z[i] = r-l+1;
        }
        else
        {
            if ( i + z[i-l+1] - 1 < r )
                z[i] = z[i-l+1];
            else
            {
                l = i;
                while ( a[r+1] == a[r-l+2] && r+1 <= n )
                    ++r;
                z[i] = r-l+1;
            }
        }
    //for (int i=1;i<=n;++i) cerr<<z[i]<<' ';
    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';
}