Cod sursa(job #2354346)

Utilizator BogdanRazvanBogdan Razvan BogdanRazvan Data 25 februarie 2019 11:01:01
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
char s1[2000005], s2[2000005];
int pref[2000005], sz1, sz2, ans[1005], k;
void prefix()
{
    int k = 0;
    pref[1] = 0;
    for(int i = 2; i <= sz1; i++) {
        while(k > 0 && s1[k + 1] != s1[i]) k = pref[k];
        if(s1[k + 1] == s1[i]) ++k;
        pref[i] = k;
    }
}
int main()
{
    fin.getline(s1 + 1, 2000003);
    fin.getline(s2 + 1, 2000003);
    sz1 = strlen(s1 + 1);
    sz2 = strlen(s2 + 1);
    prefix();
    int cnt = 0;
    for(int i = 1; i <= sz2; i++) {
        while(cnt > 0 && s2[i] != s1[cnt + 1]) cnt = pref[cnt];
        if(s2[i] == s1[cnt + 1]) ++cnt;
        if(cnt == sz1) {
            cnt = pref[sz1];
            if(k < 1000) ans[++k] = i - sz1;
            else ++k;
        }
    }
    fout << k << "\n";
    for(int i = 1; i <= min(1000, k); i++) fout << ans[i] << " ";
    return 0;
}