Cod sursa(job #1632041)

Utilizator alexmisto342Turdean Alexandru alexmisto342 Data 5 martie 2016 21:05:48
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n,i,j,m,x,y,a,b,k,z[4000005],l,r,rasp[10000];
char s[4000005];

void expand()
{
    while(s[r + 1] == s[r - l + 1] && r + 1 < n)
        r++;
}
int main()
{
    fin.get(s,2000005);
    k = strlen(s);
    s[k] = ' ';
    fin.get();
    fin.get(s+k+1,2000005);
    n = strlen(s);
    z[0] = k;
    for(i = 1; i < n; i++)
    {
        if(i>=l && i<=r)
        {
            if(z[i-l] > r-i)
            {
                l = i;
                expand();
                z[i] = r-l+1;
            }
            else
                z[i] = z[i - l];
        }
        else
            if(s[i] == s[0])
            {
                l=r=i;
                expand();
                z[i] = r-l+1;
            }
        if(z[i] == k)
        {
            rasp[0]++;
            if(rasp[0]<1001)
                rasp[ rasp[0] ] = i - k - 1;
        }
    }
    fout<<rasp[0]<<'\n';
    if(rasp[0] > 1000)
        rasp[0] = 1000;
    for(i = 1; i <= rasp[0];i++)
        fout<<rasp[i]<<" ";
    return 0;
}