Cod sursa(job #2674697)

Utilizator isa_tudor_andreiAndrei Tudor isa_tudor_andrei Data 19 noiembrie 2020 20:51:19
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

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

const int NMAX = 2000000;
const long long BASE = 256;
const long long MOD = 1e9 + 7;

char s[1 + NMAX + 1], pat[1 + NMAX + 1];
long long power = 1;

int main() {
    int n, m;
    fin>>(pat + 1)>>(s + 1);
    m = strlen(pat+1);
    n = strlen(s+1);

    long long p = 0;
    long long t = 0;
    for( int i = 1; i <= m; i ++ ) {
      p = (p * BASE + (long long)pat[i]) % MOD;
      t = (t * BASE + (long long)s[i]) % MOD;
      if( i < m )
        power = (power * BASE) % MOD;
    }

    vector<int> ans;
    for( int i = m; i <= n && ans.size() < 1000; i ++ ) {
      if( p == t ) {
        int j = 1;
        while( s[i - m + j] == pat[j] && j <= m )
          j ++;
        if( j == m + 1 )
          ans.push_back(i - m + 1);
      }
      t = ( BASE * (t - s[i - m + 1] * power + MOD) % MOD + s[i + 1] ) % MOD;
    }

    fout<<ans.size()<<"\n";
    for( int i = 0; i < ans.size(); i ++ )
      fout<<ans[i] - 1<<" ";
    return 0;
}