Cod sursa(job #1522162)

Utilizator ade_tomiEnache Adelina ade_tomi Data 11 noiembrie 2015 12:12:47
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb

#include<stdio.h>
#include<iostream>
#include<fstream>
#include<vector>
#include<cstring>

using namespace std;
int z[4000004],r,l,i,n,start,k,nr;
vector<int> sol;
string s,s2;
int main()
{
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    cin>>s;
    start=s.size();
    r=l=0;
    cin>>s2;
    s+='#';

    s+=s2;
    n=s.size();

    for(i=1;i<n;i++)
    {
        if(i>r)
        {
            l=r=i;
            while(r<n&&s[r-l]==s[r])
                r++;
            z[i]=r-l;
            r--;
        }
        else
        {
            k=i-l;

            if(z[k]+i<=r)
                z[i]=z[k];
            else
            {

                l=i;
                while(r<n&&s[r-l]==s[r]) r++;
                z[i]=r-l;
                r--;
            }
        }
    }
  //  cout<<start;
    start++;
    for(i=start;i<n;i++)
        if(z[i]==start-1)
        {

            nr++;
            if(nr<=1000)
                sol.push_back(i-start);
        }
    cout<<nr<<"\n";
    for(i=0;i<sol.size();i++)
        cout<<sol[i]<<" ";
    return 0;
}