Cod sursa(job #1242325)

Utilizator danalex97Dan H Alexandru danalex97 Data 14 octombrie 2014 12:14:17
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

ifstream F("strmatch.in");
ofstream G("strmatch.out");

const int N = 2000010;
const int cc = 1000;

string a,b;
int z[N<<1],la;

int main()
{
    F>>a>>b;
    la = a.size();
    a += b;

    int n = a.size();
    int l = 0 , r = 0;
    z[0] = n;
    for (int i=1;i<n;++i)
    {
        z[i] = 0;
        if ( l <= i && i <= r )
        {
            if ( z[i-l] >= r-i+1 ) //
            {
                l = i;
                while ( a[r+1] == a[r-l+1] && r+1 < n ) ++r;
                z[i] = r-l+1;
            }
            else
                z[i] = z[i-l];
        }
        else
            if ( a[i] == a[0] )
            {
                l = r = i;
                while ( a[r+1] == a[r-l+1] && r+1 < n ) ++r;
                z[i] = r-l+1;
            }
        //cerr<<z[i]<<' ';
    }

    vector<int> p;
    int ans = 0;
    for (int i=la;i<n;++i)
        if ( z[i] >= la )
        {
            ++ans;
            if ( p.size() < cc )
                p.push_back(i-la);
        }
    G<<ans<<'\n';
    for (int i=0;i<p.size();++i)
        G<<p[i]<<' ';
    G<<'\n';
}