Cod sursa(job #2082843)

Utilizator ssebiStanciu Sebastian ssebi Data 6 decembrie 2017 20:40:04
Problema Potrivirea sirurilor Scor 6
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string s1,s2;
vector<int> v1;
int vec[20000000];
void constuctie(int vec[],int lungime)
{
    int ok;
    int i=0,j=1;
    while(j<=lungime)
    {
        if(s1[i]==s1[j])
        {
            vec[j]=i+1;
            i++;
            j++;
        }
        else
        {
            if(i>0)
                i=vec[i-1];
            else j++;
        }
    }
}

int main()
{
    getline(f,s1);
    getline(f,s2);
    int lungime=s1.size()-1;
    int i=0;
    int j=0;
    int nr=0;
    constuctie(vec,lungime);
    while(i<s2.size())
    {
        if(s1[j]==s2[i])
        {
            j++;
            i++;
            if(j==s1.size())
            {
                nr++;
                if(nr<1001)
                v1.push_back(i-j);
                j--;
                j=vec[j];
            }
        }
        else {
        if(j!=0)
        j=vec[j];
        else i++;
        }
    }
    if(nr!=0)
    {
        g<<nr<<"\n";
        for(int i=0;i<v1.size();i++)
            g<<v1[i]<<' ';
    }

    return 0;
}