Cod sursa(job #1161433)

Utilizator Daniel3717Aleca Daniel Adrian Daniel3717 Data 31 martie 2014 11:20:34
Problema Potrivirea sirurilor Scor 4
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 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,dp[105],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++;
            }
            dp[i]=coresp;
        }
        else
        {
            equiv=i-center;
            dr2=i+dp[equiv];
            if (dr2>=dr)
            {
                center=i;
                coresp=dr-center;
                while (s[dr]==s[coresp])
                {
                    dr++;
                    coresp++;
                }
                dp[i]=coresp;
            }
            else
                dp[i]=dr2-i;
        }
        if (dp[i]==s1.size())
            r.push_back(i-s1.size()-1);
    }
    g<<r.size()<<'\n';
    for (i=0;i<r.size();i++)
        g<<r[i]<<' ';
    return 0;
}