Cod sursa(job #2014658)

Utilizator NashikAndrei Feodorov Nashik Data 24 august 2017 11:43:00
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
//#include <iostream>
#include <fstream>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
struct character
{
    char val;
    int pos;
}ch[2000005];
int vect[2000005];
char v[2000005];
int main()
{
    cin.get(ch[0].val);
    int n=0;

    while(ch[n].val!='\n')
    {
        cin.get(ch[++n].val);
    }
    ch[0].pos=0;
    int j=0,i;
    for(i=1;i<n;)
    {
        if(ch[i].val==ch[j].val)
        {
            ch[i].pos=j+1;
            i++;
            j++;
        }
        else
            if(j==0)
                {
                    ch[i].pos=0;
                    i++;
                }
            else
        {
            j=ch[j-1].pos;
        }
    }
    int m=0;
    cin.get(v[0]);
    while(v[m]!='\0')
    {
        cin.get(v[++m]);
    }
    int pozitie=0,poz=0,cnt=0;
    for(i=0;i<m;i++)
    {
        if(v[i]==ch[pozitie].val)
            {
                pozitie++;
            }
        else
        {
            if(pozitie!=0)
                pozitie--;
            pozitie=ch[pozitie].pos;
        }
        if(pozitie==n)
            {
                cnt++;
                vect[++poz]=i-pozitie+1;
                pozitie--;
                pozitie=ch[pozitie].pos;
            }

    }
    cout<<cnt<<endl;
    if(cnt>1000)
        cnt=1000;
    for(i=1;i<=cnt;i++)
        cout<<vect[i]<<" ";
    return 0;
}