Cod sursa(job #2369297)

Utilizator Tataru_AdelinTataru Adelin Tataru_Adelin Data 5 martie 2019 22:16:08
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 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(), 0);
    vector <int> ans;

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


    for(unsigned i = 0, j = 0; i < text.length();)
    {
        if(word[j] == text[i])
        {
            i++;
            j++;
        }

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

        if(i < text.length() && word[j] != text[i])
        {
            if(j != 0)
            {
                j = LPS[j - 1];
            }
            else
            {
                i++;
            }
        }
    }
    fout<<ans.size()<<'\n';
    if(ans.size() > 1000)
        for(unsigned i = 0; i < 1000; i++)
            fout<<ans[i]<<' ';
    else
        for(unsigned i = 0; i < ans.size(); i++)
            fout<<ans[i]<<' ';

    return 0;
}