Cod sursa(job #1883372)

Utilizator CalarisPredut Denis Stefanita Calaris Data 17 februarie 2017 22:18:26
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int MAX = 2000001;
int lps[MAX];

int main()
{
    string s1,s2;
    int len,i,j,len2;
    vector<int> ans;

    fstream f("strmatch.in",ios::in);
    ofstream g("strmatch.out");
    f>>s1>>s2;

    len = s1.length();
    len2 = s2.length();

    lps[0] = 0;

    i = 1;
    j=0;

    while(i!=len)
        {
          if(s1[i] == s1[j])
            {
            ++j;
            lps[i]=j;
            ++i;
            }
          else
            {
            if(j!=0)
                {
                j = lps[j-1];
                }
            else
                {
                lps[i] = 0;
                ++i;
                }
            }
        }

    i = j = 0;
    while(i<len2)
        {
        while(s1[j]==s2[i])
            {
            ++j;
            ++i;
            }
        if(j==len)
            {
            ans.push_back(i-len);
            j = lps[j-1];
            }
         else if(i <len2 && s1[j]!=s2[i])
            {
             if(j!=0)
                {
                j=lps[j-1];
                }
             else
                ++i;
            }
        }

    len = ans.size();
    g<<len<<"\n";
    j=0;
    for(i=0;i<len && j<1000;++i,++j)
        {
        g<<ans[i]<<" ";
        }

    return 0;
}