Pagini recente » Cod sursa (job #2666189) | Cod sursa (job #1966947) | Cod sursa (job #2331608) | Cod sursa (job #3224825) | Cod sursa (job #1894893)
#include <fstream>
#include <string>
#include <queue>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string txt, pat;
queue<int> indx;
int T[2000010], i, j, sol;
void precomp() {
int i = 1, j = 0;
while (i < pat.length()) {
if (pat[ i ] == pat[ j ]) {
T[ i ] = j + 1;
i++; j++;
} else if (j != 0) {
while (j != 0 && pat[ i ] != pat[ j ])
j = T[ j - 1 ];
} else {
i++;
}
}
}
int main()
{
fin >> pat >> txt;
txt.push_back('.');
precomp();
i = 0; j = 0;
while (i <= txt.length()) {
if (j >= pat.length()) {
if (indx.size() < 1000)
indx.push(i - pat.length());
sol++;
j = T[ j - 1 ];
}
if (txt[ i ] == pat[ j ]) {
i++; j++;
} else if (j != 0) {
j = T[ j - 1 ];
} else {
i++;
}
}
fout << sol << '\n';
while(!indx.empty()) {
fout << indx.front() << ' ';
indx.pop();
}
return 0;
}