Cod sursa(job #2153109)

Utilizator Tataru_AdelinTataru Adelin Tataru_Adelin Data 5 martie 2018 22:49:15
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int main()
{
    string word,text;
    fin>>word>>text;
    vector<int>LPS(word.length());
    vector<int>ans;
    int i,j;

    LPS[0]=0;
    i=1;
    j=0;
    while(i<LPS.size())
    {
        if(word[i]==word[j])
        {
            j++;
            LPS[i]=j;
            i++;
        }
        else
            if(j!=0)
            {
                j=LPS[j-1];
            }
            else
            {
                LPS[i]=0;
                i++;
            }
    }

    i=j=0;

    while(i<text.length())
    {
        if(word[j]==text[i])
        {
            i++;
            j++;
        }
        else
            if(j!=0)
            {
                j=LPS[j-1];
            }
            else
            {
                i++;
            }

        if(j==word.length())
        {
            ans.push_back(i-j);
            j=LPS[j-1];
        }
    }
    sort(ans.begin(),ans.end());

    fout<<ans.size()<<'\n';
    if(ans.size()>1000)
        for(int i=0;i<1000;i++)
            fout<<ans[i]<<' ';
    else
        for(int i=0;i<ans.size();i++)
            fout<<ans[i]<<' ';
    fout<<'\n';

    return 0;
}