Cod sursa(job #1161467)

Utilizator Daniel3717Aleca Daniel Adrian Daniel3717 Data 31 martie 2014 11:30:46
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
string s,s1,s2;
vector <int> r;
int center,dr,i,dr2,coresp,z[4000015],equiv;
int main(void)
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    f>>s1>>s2;
    s=s1+"*"+s2;
    for (i=1;i<s.size();i++)
    {
        if (i>=dr)
        {
            center=i;
            dr=i;
            coresp=0;
            while (s[dr]==s[coresp])
            {
                dr++;
                coresp++;
            }
            z[i]=coresp;
        }
        else
        {
            equiv=i-center;
            dr2=i+z[equiv];
            if (dr2>=dr)
            {
                center=i;
                coresp=dr-center;
                while (s[dr]==s[coresp])
                {
                    dr++;
                    coresp++;
                }
                z[i]=coresp;
            }
            else
                z[i]=dr2-i;
        }
        if (z[i]==s1.size())
            r.push_back(i-s1.size()-1);
    }
    g<<r.size()<<'\n';
    for (i=0;(i<r.size())&&(i<1000);i++)
        g<<r[i]<<' ';
    g<<'\n';
    return 0;
}