Pagini recente » Cod sursa (job #537689) | Cod sursa (job #826477) | Cod sursa (job #1955905) | Cod sursa (job #3222265) | Cod sursa (job #2041700)
#include <bits/stdc++.h>
using namespace std ;
ifstream fin ("strmatch.in") ;
ofstream fout ("strmatch.out") ;
const int MAX = 4e6 + 14 ;
char sir [MAX] ; // string concatenated
int main(int argc, char const *argv[])
{
fin >> (sir + 1) ;
int patternSize = strlen (sir + 1) ;
sir [patternSize + 1] = '#' ;
fin >> (sir + patternSize + 1) ;
int totalLength = strlen (sir + 1) ;
vector <int> pi (totalLength + 1, 0) ;
vector <int> sol ;
int noSol = 0 ;
for (int i = 2 ; i <= totalLength ; ++ i) {
int k = pi [i - 1] ;
while (k and sir [k + 1] != sir [i]) {
k = pi [k] ;
}
if (sir [k + 1] == sir [i]) {
k += 1 ;
}
pi [i] = k ;
if (pi [i] == patternSize) {
noSol += 1 ;
if (noSol <= 1000) {
sol.push_back (i - 2 * patternSize) ;
}
}
}
fout << noSol << '\n' ;
for (auto &x : sol) {
fout << x << ' ' ;
}
return 0;
}