Cod sursa(job #2356513)

Utilizator triscacezarTrisca Vicol Cezar triscacezar Data 26 februarie 2019 19:01:31
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

int n,i,k,kmp[100010];
vector<int> ans;
string S1,S2;

int main()
{
    f>>S1>>S2;
    n=S1.size();
    for(i=2;i<=n;i++)
    {
        while((S1[k]!=S1[i-1])&&k)
            k=kmp[k];
        if(S1[k]==S1[i-1])
            k++;
        kmp[i]=k;
    }
    k=0;
    n=S2.size();
    for(i=1;i<=n;i++)
    {
        while(S1[k]!=S2[i-1]&&k)
            k=kmp[k];
        if(S1[k]==S2[i-1])
            k++;
        if(k==S1.size())
            ans.push_back(i);
    }
    g<<ans.size()<<'\n';
    for(i=0;i<1000&&i<ans.size();i++)
        g<<ans[i]-S1.size()<<' ';
    return 0;
}